1 00:00:00,451 --> 00:00:05,521 [MUSIC]. 2 00:00:05,521 --> 00:00:09,613 We just saw how we store and access basic arrays in memory by putting all of their 3 00:00:09,613 --> 00:00:15,191 elements one right after the other in a continuous block of memory. 4 00:00:15,191 --> 00:00:19,111 In the, this video, we're going to take a look at multidimensional arrays or nested 5 00:00:19,111 --> 00:00:22,530 arrays, where we have more than one dimension. 6 00:00:22,530 --> 00:00:26,517 So, let's take a look at a quick example here. 7 00:00:26,517 --> 00:00:31,990 let's continue with our ZIP code motive. Here, we have an array that's 8 00:00:31,990 --> 00:00:38,470 two-dimensional it's it's nesting the ZIP codes of multiple locations in a single 9 00:00:38,470 --> 00:00:43,402 array. So here, we see four different ZIP codes 10 00:00:43,402 --> 00:00:49,050 contained in an in an array. Each one of which has five elements, the 11 00:00:49,050 --> 00:00:55,254 five digits of the ZIP code. so remember that in our declarations, 12 00:00:55,254 --> 00:01:02,730 when we write an array of some type with its name and number of elements. 13 00:01:02,730 --> 00:01:08,872 here we see that the number of elements is this value PCOUNT which is defined in 14 00:01:08,872 --> 00:01:15,530 our c code as being a four. the name of the array is Sea probably 15 00:01:15,530 --> 00:01:21,380 meaning zip codes in Seattle. And the type is zip digit. 16 00:01:21,380 --> 00:01:24,980 the type we have seen before for representing the five digits of a zip 17 00:01:24,980 --> 00:01:28,597 code. So here we have our four zip codes each 18 00:01:28,597 --> 00:01:33,342 represented on a separate line. You'll notice there's closing brackets 19 00:01:33,342 --> 00:01:37,080 around all four. that define the entire array. 20 00:01:38,550 --> 00:01:43,039 The way this is stored in memory is also contiguously but, we have to decide of 21 00:01:43,039 --> 00:01:47,600 course how to store the multiple zip codes now. 22 00:01:47,600 --> 00:01:52,601 So, you'll see we have one zip code here. I, again, arbitrarily starting at an 23 00:01:52,601 --> 00:01:56,160 address 76. but that could be anything. 24 00:01:56,160 --> 00:02:01,230 It's it depends on how memory is allocated in our system. 25 00:02:01,230 --> 00:02:04,950 here we see the five zip codes of that first value 98195. 26 00:02:04,950 --> 00:02:08,541 And then, it's immediately followed by the next one, and the next one and the 27 00:02:08,541 --> 00:02:15,010 next one. and these are in what is called row major 28 00:02:15,010 --> 00:02:19,649 order. In other words, we've taken one row of 29 00:02:19,649 --> 00:02:24,341 the array and completely put that into memory, one right after the other, as if 30 00:02:24,341 --> 00:02:30,874 it was a one dimensional array, and then follow that by the next row. 31 00:02:30,874 --> 00:02:36,860 and all its five elements, and then the next row and its five elements and so on. 32 00:02:36,860 --> 00:02:40,470 This is a guaranteed organization in memory. 33 00:02:40,470 --> 00:02:45,369 We can rely on this. so when we write something like this 34 00:02:45,369 --> 00:02:52,362 access to the C sea 3 2 that means we want the fourth row the index three 35 00:02:52,362 --> 00:03:03,261 starting at 0 so it's the fourth row. And then the third digit within that 36 00:03:03,261 --> 00:03:09,220 within that row, within that zip code, or that zip dig type. 37 00:03:09,220 --> 00:03:14,195 And that's the the number one represented in that location. 38 00:03:14,195 --> 00:03:17,020 Okay. Alright. 39 00:03:17,020 --> 00:03:21,040 So in general when we talk about multidimensional arrays and in this state 40 00:03:21,040 --> 00:03:25,000 we're still looking just at purely two dimensional, we have a number of rows and 41 00:03:25,000 --> 00:03:28,480 a number of columns and in our declaration we can just put two brackets 42 00:03:28,480 --> 00:03:34,925 right after the other. one with the number of rows, one with the 43 00:03:34,925 --> 00:03:38,524 number of columns that's going to generate that two dimensional array as 44 00:03:38,524 --> 00:03:44,170 we've seen in the previous example with r rows and c columns. 45 00:03:44,170 --> 00:03:48,856 Each element of that array is going to require k bytes to represent whatever the 46 00:03:48,856 --> 00:03:53,980 size of that element is. in the case of the digits it was a simple 47 00:03:53,980 --> 00:04:00,130 integer, it was just a four bytes. but that could really be any data 48 00:04:00,130 --> 00:04:04,792 structure, okay. So our array then in general is of size R 49 00:04:04,792 --> 00:04:09,428 times C times K, where R and C are the rows and columns, and K is the size of an 50 00:04:09,428 --> 00:04:16,560 element. And again, arranged in row-major order. 51 00:04:16,560 --> 00:04:23,040 So we see the very first element here at at 00 the two indexes and then that will 52 00:04:23,040 --> 00:04:31,255 be followed by 01, 02, all the way to 0C minus 1 in this location. 53 00:04:31,255 --> 00:04:38,260 Okay, then we start the next row, with starting index of 10. 54 00:04:38,260 --> 00:04:43,600 All the way to one C minus one and then we'll put the next row after that. 55 00:04:43,600 --> 00:04:50,300 Eventually, we'll have the last row, represented by those indexes, okay? 56 00:04:50,300 --> 00:04:54,992 And if we're talking about integers as in this case here, we've declared an integer 57 00:04:54,992 --> 00:05:00,182 array, then this size of this entire area of memory will be. 58 00:05:00,182 --> 00:05:06,630 Four times the number of rows times the number of columns. 59 00:05:06,630 --> 00:05:08,820 Okay. So how do we access, the elements of this 60 00:05:08,820 --> 00:05:10,430 array? well, again. 61 00:05:10,430 --> 00:05:15,060 Let's start with the starting address of the array. 62 00:05:15,060 --> 00:05:19,780 the starting address of the array is, represented by the name of the array. 63 00:05:19,780 --> 00:05:25,159 A, in this case. And the very next row of the array is 64 00:05:25,159 --> 00:05:32,668 going to be how far down in memory. Well, it's gotta represent all of the 65 00:05:32,668 --> 00:05:37,810 columns in that row and then the size of the data element. 66 00:05:37,810 --> 00:05:44,300 So, every row is of this size, number of columns times the size of the element. 67 00:05:44,300 --> 00:05:50,410 And then of course the index is used as a multiplier on, on that. 68 00:05:50,410 --> 00:05:54,800 In this case again, for integers, K is four, and we're multiplying by the index. 69 00:05:54,800 --> 00:05:59,825 So the very the, the rows starting at index one, which is the second row, would 70 00:05:59,825 --> 00:06:04,460 be at A plus C times 4. Okay. 71 00:06:04,460 --> 00:06:11,240 The very last row would be at a plus r minus one times c times four. 72 00:06:11,240 --> 00:06:16,198 And, we could easily have the starting address of each row by doing that basic 73 00:06:16,198 --> 00:06:21,221 arithmetic. Okay, so let's, take a look at an example 74 00:06:21,221 --> 00:06:24,987 here. Here's our array again, that we saw 75 00:06:24,987 --> 00:06:30,860 earlier, a four by five array, a four zip codes of five digits each. 76 00:06:30,860 --> 00:06:37,470 And we have here, a little procedure that returns a pointer to an integer, okay? 77 00:06:37,470 --> 00:06:42,642 And is given an index as an argument and what it does, is it returns. 78 00:06:42,642 --> 00:06:49,887 the starting address, the pointer to the starting address of the zip code at that 79 00:06:49,887 --> 00:06:54,971 index. Okay, so if we ask for the, the zero with 80 00:06:54,971 --> 00:06:59,640 a zip code we would return the starting address. 81 00:06:59,640 --> 00:07:03,680 If we ask for the first zip code or the second element. 82 00:07:03,680 --> 00:07:09,670 at index one we would return the starting address of the second row. 83 00:07:09,670 --> 00:07:10,320 And so on. 'Kay. 84 00:07:10,320 --> 00:07:16,628 The code for implementing that basic little pointer returning procedure, is to 85 00:07:16,628 --> 00:07:21,670 compute an address. So we use that effective address 86 00:07:21,670 --> 00:07:26,678 computation instruction. And you'll see here that what we're doing 87 00:07:26,678 --> 00:07:31,445 is taking the index, that was in EAX and multiplying it by five. 88 00:07:31,445 --> 00:07:34,970 Okay. And we can do that using that leal 89 00:07:34,970 --> 00:07:39,776 instruction. Then we take that index, that value five 90 00:07:39,776 --> 00:07:44,550 times the index and multiply it by another four. 91 00:07:44,550 --> 00:07:47,783 Remember, because we can only put powers of two in that loca-, in that, 92 00:07:47,783 --> 00:07:51,122 instruction, we can't just multiply by 20, right off the bat, so we have to do 93 00:07:51,122 --> 00:07:56,230 it in two steps. We get 20 times the index. 94 00:07:56,230 --> 00:07:58,790 And why do we go after 20 times the index? 95 00:07:58,790 --> 00:08:02,630 Well, because we're going to have five elements in each row, and the elements of 96 00:08:02,630 --> 00:08:08,148 size of four, they're just integers. So that means each row is of size 20, 97 00:08:08,148 --> 00:08:12,324 okay, and we're going to do 20 times the index and add that to the starting 98 00:08:12,324 --> 00:08:16,644 address of the array and I've just shown it here as the offset for the leal 99 00:08:16,644 --> 00:08:21,834 instruction. Okay. 100 00:08:21,834 --> 00:08:29,125 so that's the starting address that's computed and returned by this procedure. 101 00:08:29,125 --> 00:08:32,765 All right, we have to do it in two steps again, because of the constraints on the 102 00:08:32,765 --> 00:08:37,662 leal instruction. All right, let's go another step further 103 00:08:37,662 --> 00:08:43,830 and look at how would we compute the address of a particular element? 104 00:08:43,830 --> 00:08:48,180 Let's say element aij for the most general case. 105 00:08:48,180 --> 00:08:53,206 Okay, so, how would we compute that. Well to compute that address we would 106 00:08:53,206 --> 00:08:57,420 first have to get to the beginning of the row, right? 107 00:08:57,420 --> 00:09:04,010 And then do an offset within the row to get to the address of that array. 108 00:09:04,010 --> 00:09:07,980 So you'll see that our address is the starting address of the array. 109 00:09:07,980 --> 00:09:12,710 Actually, that gets us here. To begin with. 110 00:09:12,710 --> 00:09:17,919 And then we have to offset by the number of rows that we're going in. 111 00:09:17,919 --> 00:09:24,005 So our first index, the number of rows times the column times the size. 112 00:09:24,005 --> 00:09:28,610 Remember, C times K is much space a row takes up. 113 00:09:28,610 --> 00:09:31,800 And then we just multiply that by the number of rows we need to offset. 114 00:09:31,800 --> 00:09:36,800 We're now at this point. And then we need the offset within the 115 00:09:36,800 --> 00:09:41,760 row, and for that we need the second index j, the number of the column, times 116 00:09:41,760 --> 00:09:48,745 the size of the element. And that will get us in as far as we need 117 00:09:48,745 --> 00:09:55,373 to go to get to the I, ij element. Okay, so, in general, we can simplify 118 00:09:55,373 --> 00:09:59,910 that to that expression, i times c plus j times k. 119 00:09:59,910 --> 00:10:05,085 And then offset that from the starting address of the array. 120 00:10:05,085 --> 00:10:08,961 Alright, let's go back to our example, but now we have, a, a different 121 00:10:08,961 --> 00:10:13,475 procedure. same array, but a different procedure 122 00:10:13,475 --> 00:10:18,031 that computes this time just, an integer that is the particular digit of one of 123 00:10:18,031 --> 00:10:22,884 the zip codes. So this takes two arguments, the index as 124 00:10:22,884 --> 00:10:26,711 well as the digit. that we want the third digit or the 125 00:10:26,711 --> 00:10:30,580 fourth digit so on. It returns an int of course. 126 00:10:30,580 --> 00:10:34,108 Because now we're not going to be returning an address, we're going to be 127 00:10:34,108 --> 00:10:39,540 returning the actual value of that digit of the zip code. 128 00:10:39,540 --> 00:10:45,258 Okay, so, let's take a look at the At the C code for this that's pretty 129 00:10:45,258 --> 00:10:48,985 simple. We first index into the row of the array, 130 00:10:48,985 --> 00:10:53,565 and then to the right column, or to the right digit position. 131 00:10:53,565 --> 00:10:56,700 Okay. The way this is represented in in 132 00:10:56,700 --> 00:11:00,600 assembly language is using a couple of leal instructions and then a move 133 00:11:00,600 --> 00:11:06,420 instruction to actually get that digit. value out of memory. 134 00:11:06,420 --> 00:11:10,864 And let's see how we do that. Assuming that we put the digit in ecx at 135 00:11:10,864 --> 00:11:15,715 the beginning, what we'll do is use an leal instruction to just compute four 136 00:11:15,715 --> 00:11:22,590 times that index. That would be like J times four, okay. 137 00:11:22,590 --> 00:11:27,951 to get us the offset within the row. Then we need the offset to the right row, 138 00:11:27,951 --> 00:11:32,440 and remember what is that, that is just that 20 times the first index again, so, 139 00:11:32,440 --> 00:11:38,993 here we do that, times five. And then we're going to have to multiply 140 00:11:38,993 --> 00:11:43,590 that by four and we'll do that as we do the actual memory access. 141 00:11:43,590 --> 00:11:49,750 So you'll see here, we'll take that five times the first index, five times i value 142 00:11:49,750 --> 00:11:55,734 and multiply it by four to get 20 times i or 20 times the index add it to, add to 143 00:11:55,734 --> 00:12:03,920 that the four times digit that we stored in edx. 144 00:12:03,920 --> 00:12:07,448 And that gives us the complete offset into the array and then we just need the 145 00:12:07,448 --> 00:12:11,170 starting address of the array to add that to. 146 00:12:11,170 --> 00:12:15,832 to, to get us to the right memory location, we get the value at that memory 147 00:12:15,832 --> 00:12:22,870 location and store it in eax. ready for returning from our procedure. 148 00:12:22,870 --> 00:12:26,469 Alright, so that's the general process and you'll see, these kinds of 149 00:12:26,469 --> 00:12:30,658 expressions often, these little groups of instructions that compute an address and 150 00:12:30,658 --> 00:12:36,888 then go and actually access the memory. Let's close this up with some addressing 151 00:12:36,888 --> 00:12:41,568 examples, different accesses to our array, here we have our array shown again 152 00:12:41,568 --> 00:12:48,220 as it's represented in memory. a continuous part of memory. 153 00:12:48,220 --> 00:12:54,281 And let's look at our first access 3, 3. looking at that location, what, what 154 00:12:54,281 --> 00:12:59,000 address should that be? Well, remember, we have to get, multiply 155 00:12:59,000 --> 00:13:04,220 that first index by 20, so that would three times 20, or 60. 156 00:13:04,220 --> 00:13:07,460 And then the second index is multiplied by 4. 157 00:13:07,460 --> 00:13:12,854 The offset within the row so that's another 12 so it'd be 72 total plus the 158 00:13:12,854 --> 00:13:19,314 starting address of the array at 76 which puts us at 148. 159 00:13:19,314 --> 00:13:25,035 And the value of that element is this one right here, the one. 160 00:13:25,035 --> 00:13:29,139 Remember, it's the fourth row, the fourth element because of our indices are off by 161 00:13:29,139 --> 00:13:32,810 one. They start at zero. 162 00:13:32,810 --> 00:13:36,050 So, we see that the address is 148, the value is one. 163 00:13:36,050 --> 00:13:40,076 And this is in fact guaranteed because of our row major order for how we store 164 00:13:40,076 --> 00:13:45,752 these arrays. Our next example is sea 25. 165 00:13:45,752 --> 00:13:51,680 and you'll notice that, that five seems to be out of bounds. 166 00:13:51,680 --> 00:13:55,254 It's too high an index for our array. We would only expect to go up as high as 167 00:13:55,254 --> 00:14:00,054 four for the fifth element. So, this is probably not a correct 168 00:14:00,054 --> 00:14:04,886 construct, but in C the same address computation is done. 169 00:14:04,886 --> 00:14:10,946 so it doesn't check for those bounds. So, what, what happened in this case is 170 00:14:10,946 --> 00:14:15,978 we would compute an address based on that first index times 20 and the second index 171 00:14:15,978 --> 00:14:20,618 times four. Adding all that up we get 136 as our 172 00:14:20,618 --> 00:14:24,040 address. And the value is nine. 173 00:14:24,040 --> 00:14:28,504 And the 136 you'll notice is this location, right, which is clearly not the 174 00:14:28,504 --> 00:14:33,143 third element that we seem to be looking for here. 175 00:14:33,143 --> 00:14:35,940 The third row. it's one beyond that. 176 00:14:35,940 --> 00:14:39,960 But because of how we arrange things in memory, and row major order, we will in 177 00:14:39,960 --> 00:14:45,017 fact always get a nine. And this value is guaranteed to be 178 00:14:45,017 --> 00:14:50,612 consistent. even though we're using the wrong index. 179 00:14:50,612 --> 00:14:54,833 Similarly with the next one, with the minus one for an index, which is clearly 180 00:14:54,833 --> 00:14:59,643 out of bounds. but the same address computation is done, 181 00:14:59,643 --> 00:15:06,070 this time yielding 112, or one before. our row of interest. 182 00:15:06,070 --> 00:15:10,291 And the value there is five. And again, that's guaranteed because of 183 00:15:10,291 --> 00:15:17,570 the row major organization. When we do 4 minus 1 that's again a 184 00:15:17,570 --> 00:15:25,214 little bit out of bounds. We've gone beyond the memory, but because 185 00:15:25,214 --> 00:15:29,972 of the minus 1 we get, we yield an address of 152, which is this location 186 00:15:29,972 --> 00:15:34,511 here. And the number 5 is guaranteed to be 187 00:15:34,511 --> 00:15:36,126 there. Okay. 188 00:15:36,126 --> 00:15:43,406 Finally 019 address computation is that same exact location done in a very funny 189 00:15:43,406 --> 00:15:47,698 way. We've sort of gone over the bounds of our 190 00:15:47,698 --> 00:15:51,940 first row, and just kept going and ended up in the same location. 191 00:15:51,940 --> 00:15:57,295 While the previous one, 4 minus 1, we actually started one outside the array 192 00:15:57,295 --> 00:16:02,690 and came back in and looked at that last element. 193 00:16:02,690 --> 00:16:07,200 but that, those are in fact addressing the same location. 194 00:16:07,200 --> 00:16:12,384 The last example here of course 0 minus 1 puts us at this location and minus 1 from 195 00:16:12,384 --> 00:16:17,420 that, and that would be the location here. 196 00:16:17,420 --> 00:16:20,680 for which we have no idea what is in that location. 197 00:16:20,680 --> 00:16:24,097 And there's no guarantee as to what we'll find there because it depends on how 198 00:16:24,097 --> 00:16:29,109 things are arranged in memory. So the important thing from this is that 199 00:16:29,109 --> 00:16:33,197 number row major order for the order in which things are arranged in 200 00:16:33,197 --> 00:16:38,332 multidimensional arrays. and we can actually use that to our 201 00:16:38,332 --> 00:16:41,777 advantage sometimes, but it's probably best to stick that with the ray bounds 202 00:16:41,777 --> 00:16:44,200 that are within range.