[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 oczut informatyk12[01] 02 101introligators4[02] z2 01 n02 martenzytyczne1OBRECZE MS OK 0202 Gametogeneza02 07Wyk ad 02r01 02 popr (2)Arrays1) 25 02 2012więcej podobnych podstron