[MUSIC]. We just saw how we store and access basic arrays in memory by putting all of their elements one right after the other in a continuous block of memory. In the, this video, we're going to take a look at multidimensional arrays or nested arrays, where we have more than one dimension. So, let's take a look at a quick example here. let's continue with our ZIP code motive. Here, we have an array that's two-dimensional it's it's nesting the ZIP codes of multiple locations in a single array. So here, we see four different ZIP codes contained in an in an array. Each one of which has five elements, the five digits of the ZIP code. so remember that in our declarations, when we write an array of some type with its name and number of elements. here we see that the number of elements is this value PCOUNT which is defined in our c code as being a four. the name of the array is Sea probably meaning zip codes in Seattle. And the type is zip digit. the type we have seen before for representing the five digits of a zip code. So here we have our four zip codes each represented on a separate line. You'll notice there's closing brackets around all four. that define the entire array. The way this is stored in memory is also contiguously but, we have to decide of course how to store the multiple zip codes now. So, you'll see we have one zip code here. I, again, arbitrarily starting at an address 76. but that could be anything. It's it depends on how memory is allocated in our system. here we see the five zip codes of that first value 98195. And then, it's immediately followed by the next one, and the next one and the next one. and these are in what is called row major order. In other words, we've taken one row of the array and completely put that into memory, one right after the other, as if it was a one dimensional array, and then follow that by the next row. and all its five elements, and then the next row and its five elements and so on. This is a guaranteed organization in memory. We can rely on this. so when we write something like this access to the C sea 3 2 that means we want the fourth row the index three starting at 0 so it's the fourth row. And then the third digit within that within that row, within that zip code, or that zip dig type. And that's the the number one represented in that location. Okay. Alright. So in general when we talk about multidimensional arrays and in this state we're still looking just at purely two dimensional, we have a number of rows and a number of columns and in our declaration we can just put two brackets right after the other. one with the number of rows, one with the number of columns that's going to generate that two dimensional array as we've seen in the previous example with r rows and c columns. Each element of that array is going to require k bytes to represent whatever the size of that element is. in the case of the digits it was a simple integer, it was just a four bytes. but that could really be any data structure, okay. So our array then in general is of size R times C times K, where R and C are the rows and columns, and K is the size of an element. And again, arranged in row-major order. So we see the very first element here at at 00 the two indexes and then that will be followed by 01, 02, all the way to 0C minus 1 in this location. Okay, then we start the next row, with starting index of 10. All the way to one C minus one and then we'll put the next row after that. Eventually, we'll have the last row, represented by those indexes, okay? And if we're talking about integers as in this case here, we've declared an integer array, then this size of this entire area of memory will be. Four times the number of rows times the number of columns. Okay. So how do we access, the elements of this array? well, again. Let's start with the starting address of the array. the starting address of the array is, represented by the name of the array. A, in this case. And the very next row of the array is going to be how far down in memory. Well, it's gotta represent all of the columns in that row and then the size of the data element. So, every row is of this size, number of columns times the size of the element. And then of course the index is used as a multiplier on, on that. In this case again, for integers, K is four, and we're multiplying by the index. So the very the, the rows starting at index one, which is the second row, would be at A plus C times 4. Okay. The very last row would be at a plus r minus one times c times four. And, we could easily have the starting address of each row by doing that basic arithmetic. Okay, so let's, take a look at an example here. Here's our array again, that we saw earlier, a four by five array, a four zip codes of five digits each. And we have here, a little procedure that returns a pointer to an integer, okay? And is given an index as an argument and what it does, is it returns. the starting address, the pointer to the starting address of the zip code at that index. Okay, so if we ask for the, the zero with a zip code we would return the starting address. If we ask for the first zip code or the second element. at index one we would return the starting address of the second row. And so on. 'Kay. The code for implementing that basic little pointer returning procedure, is to compute an address. So we use that effective address computation instruction. And you'll see here that what we're doing is taking the index, that was in EAX and multiplying it by five. Okay. And we can do that using that leal instruction. Then we take that index, that value five times the index and multiply it by another four. Remember, because we can only put powers of two in that loca-, in that, instruction, we can't just multiply by 20, right off the bat, so we have to do it in two steps. We get 20 times the index. And why do we go after 20 times the index? Well, because we're going to have five elements in each row, and the elements of size of four, they're just integers. So that means each row is of size 20, okay, and we're going to do 20 times the index and add that to the starting address of the array and I've just shown it here as the offset for the leal instruction. Okay. so that's the starting address that's computed and returned by this procedure. All right, we have to do it in two steps again, because of the constraints on the leal instruction. All right, let's go another step further and look at how would we compute the address of a particular element? Let's say element aij for the most general case. Okay, so, how would we compute that. Well to compute that address we would first have to get to the beginning of the row, right? And then do an offset within the row to get to the address of that array. So you'll see that our address is the starting address of the array. Actually, that gets us here. To begin with. And then we have to offset by the number of rows that we're going in. So our first index, the number of rows times the column times the size. Remember, C times K is much space a row takes up. And then we just multiply that by the number of rows we need to offset. We're now at this point. And then we need the offset within the row, and for that we need the second index j, the number of the column, times the size of the element. And that will get us in as far as we need to go to get to the I, ij element. Okay, so, in general, we can simplify that to that expression, i times c plus j times k. And then offset that from the starting address of the array. Alright, let's go back to our example, but now we have, a, a different procedure. same array, but a different procedure that computes this time just, an integer that is the particular digit of one of the zip codes. So this takes two arguments, the index as well as the digit. that we want the third digit or the fourth digit so on. It returns an int of course. Because now we're not going to be returning an address, we're going to be returning the actual value of that digit of the zip code. Okay, so, let's take a look at the At the C code for this that's pretty simple. We first index into the row of the array, and then to the right column, or to the right digit position. Okay. The way this is represented in in assembly language is using a couple of leal instructions and then a move instruction to actually get that digit. value out of memory. And let's see how we do that. Assuming that we put the digit in ecx at the beginning, what we'll do is use an leal instruction to just compute four times that index. That would be like J times four, okay. to get us the offset within the row. Then we need the offset to the right row, and remember what is that, that is just that 20 times the first index again, so, here we do that, times five. And then we're going to have to multiply that by four and we'll do that as we do the actual memory access. So you'll see here, we'll take that five times the first index, five times i value and multiply it by four to get 20 times i or 20 times the index add it to, add to that the four times digit that we stored in edx. And that gives us the complete offset into the array and then we just need the starting address of the array to add that to. to, to get us to the right memory location, we get the value at that memory location and store it in eax. ready for returning from our procedure. Alright, so that's the general process and you'll see, these kinds of expressions often, these little groups of instructions that compute an address and then go and actually access the memory. Let's close this up with some addressing examples, different accesses to our array, here we have our array shown again as it's represented in memory. a continuous part of memory. And let's look at our first access 3, 3. looking at that location, what, what address should that be? Well, remember, we have to get, multiply that first index by 20, so that would three times 20, or 60. And then the second index is multiplied by 4. The offset within the row so that's another 12 so it'd be 72 total plus the starting address of the array at 76 which puts us at 148. And the value of that element is this one right here, the one. Remember, it's the fourth row, the fourth element because of our indices are off by one. They start at zero. So, we see that the address is 148, the value is one. And this is in fact guaranteed because of our row major order for how we store these arrays. Our next example is sea 25. and you'll notice that, that five seems to be out of bounds. It's too high an index for our array. We would only expect to go up as high as four for the fifth element. So, this is probably not a correct construct, but in C the same address computation is done. so it doesn't check for those bounds. So, what, what happened in this case is we would compute an address based on that first index times 20 and the second index times four. Adding all that up we get 136 as our address. And the value is nine. And the 136 you'll notice is this location, right, which is clearly not the third element that we seem to be looking for here. The third row. it's one beyond that. But because of how we arrange things in memory, and row major order, we will in fact always get a nine. And this value is guaranteed to be consistent. even though we're using the wrong index. Similarly with the next one, with the minus one for an index, which is clearly out of bounds. but the same address computation is done, this time yielding 112, or one before. our row of interest. And the value there is five. And again, that's guaranteed because of the row major organization. When we do 4 minus 1 that's again a little bit out of bounds. We've gone beyond the memory, but because of the minus 1 we get, we yield an address of 152, which is this location here. And the number 5 is guaranteed to be there. Okay. Finally 019 address computation is that same exact location done in a very funny way. We've sort of gone over the bounds of our first row, and just kept going and ended up in the same location. While the previous one, 4 minus 1, we actually started one outside the array and came back in and looked at that last element. but that, those are in fact addressing the same location. The last example here of course 0 minus 1 puts us at this location and minus 1 from that, and that would be the location here. for which we have no idea what is in that location. And there's no guarantee as to what we'll find there because it depends on how things are arranged in memory. So the important thing from this is that number row major order for the order in which things are arranged in multidimensional arrays. and we can actually use that to our advantage sometimes, but it's probably best to stick that with the ray bounds that are within range.

Wyszukiwarka

Podobne podstrony:
Margit Sandemo Cykl Saga o czarnoksiężniku (02) Blask twoich oczu
t informatyk12[01] 02 101
introligators4[02] z2 01 n
02 martenzytyczne1
OBRECZE MS OK 02
02 Gametogeneza
02 07
Wyk ad 02
r01 02 popr (2)
Arrays
1) 25 02 2012

więcej podobnych podstron