
\documentclass[11pt]{article}

\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\topmargin}{0.0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0.5in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.0in}
\setlength{\parindent}{0in}
\setlength{\parskip}{0.1in}

\usepackage{times}
\usepackage{fancyheadings}

\begin{document}

\pagestyle{fancy}
\cfoot{Data and Data Storage: \thepage}

\title{Information Representation and Storage}

\author{Norman Matloff \\
University of California at Davis}

\date{October 12, 1999}

\maketitle

\tableofcontents

\section{Overview}

A computer can store many types of information.  A high-level
language (HLL) will typically have several data types, such as
the C language's {\bf int}, {\bf float}, and {\bf char}.
Yet a computer cannot directly store any of these data types.
Instead, a computer only stores 0s and 1s.  In this document,
we will address several questions related to this point:

\begin{itemize}

\item 

How one can represent the abstract data types of C or other HLLs in
terms of 0s and 1s.  What, for example, does a {\bf char} variable look
like when viewed from ``under the hood''?  

\item

Where are variables are stored, i.e. where they are placed within the
structure of a computer's main memory?

\item

What are the implications for hardware design, and the relative roles
of hardware and software?

\end{itemize}  




\section{Representations in Bit Strings}

We will review the following questions: How can the various abstract
data types used in HLLs, and also the computer's machine instructions,
be represented using 0s and 1s?  

\subsection{Representing Integer Data}

Representing nonnegative integer values is straightforward:  We 
just use the base-2 representation, such as 010 for the number +2.  
For example, the C language data type {\bf unsigned int} (also called
simply {\bf unsigned}) uses this representation.

But what about integers which can be either positive or negative, i.e.
which are signed?  For example, what about the data type {\bf int} in C?
In most systems today, 2s-complement storage is used.  The reader may
already be familiar with the ``formula'' to interchange 1s and 0s and
then add 1, but it is also important to understand the intuition behind
the 2s-complement system.

To explain how the system works, first think of strings of three decimal
digits, instead of three bits.  For concreteness, think of a 3-digit
odometer or trip meter in an automobile.  Think about how we could store
positive and negative numbers on this trip meter, if we had the desire
to do so.  Since there are 10 choices for each digit (0,1,...,9), and
there are three digits, there are $10^3 = 1000$ possible patterns.  So,
we would be able to store numbers which are approximately in the range
-500 to +500.

Suppose we can wind the odometer forward or backward with some manual
control.  Let us initially set the odometer to 000, i.e. set all
three digits to 0.  If we were to wind {\bf  forward} from 000 once,
we would get 001; if we were to wind forward from 000 twice, we would
get 002; and so on.  So we would use the odometer pattern 000 to
represent 0, 001 to represent +1, 002 to represent +2, ..., and 499
to represent +499.  If we were to wind {\bf  backward} from 000 once,
we would get 999; if we were to wind backward twice, we would get 998;
and so on.  So we would use the odometer pattern 999 to represent -1,
use 998 to represent -2, ..., and use 500 to represent -500 (since
the odometer would read 500 if we were to wind backward 500 times).
This would give us a range -500 to +499 of representable numbers.

Getting back to strings of three binary digits instead of three
decimal digits, we apply the same principle.  If we wind backward
once from 000, we get 111, so we use 111 to represent -1.  If we wind
backward twice from 000, we get 110, so 110 will be used to represent
-2.  Similarly, 101 will mean -3, and 100 will mean -4.  If we wind
backward one more time, we get 011, which we already reserved to
represent +3, so -4 will be our most negative representable number.
So, under the 2's complement system, 3-bit strings can represent any
integer in the range -4 to +3.

This may at first seem to the reader like a strange system, but it
has a very powerful advantage:  We can do addition of two numbers
without worrying about their signs; whether the two addends are both
positive, both negative or of mixed signs, we will do addition in the
same manner.  For example, look at the base-10 case above, and
suppose we wish to add +23 and -6.  These have the ``trip meter''
representations 023 and 994.  Adding 023 and 994 yields 1017, but
since we are working with 3-digit quantities, the leading 1 in 1017
is lost, and we get 017.  017 is the ``trip meter'' representation of
+17, so our answer is +17---exactly as it should be, since we wanted
to add +23 and -6.  The reason this works is that we have first
wound forward 23 times (to 023) but then wound backward 6 times
(the 994), for a net winding forward 17 times.

The importance of this is that in building a computer, the hardware
to do addition is greatly simplified.  The same hardware will work
for all cases of signs of addends.  For this reason, most modern
computers are designed to use the 2's-complement system.

\subsection{Representing Real Number Data}
\label{float}

Variables of type {\bf float} in C are stored in {\bf  floating-point}
format.  The main idea here is to use {\bf scientific notation},
familiar from physics or chemistry, say $3.2 \times 10^{-4}$ for the
number 0.00032.  In this example, 3.2 is called the {\bf mantissa} and
-4 is called the {\bf exponent}.  

The same idea is used to store real numbers, i.e. numbers which are
not necessarily integers (also called {\bf floating-point} numbers), in
a computer.  The representation is essentially of the form
 
$$
m \times 2^n ,
$$
 
Let us illustrate this with a very simple example.  Suppose we are
storing floating-point numbers in 6-bit strings, with the leftmost (i.e. most
significant) 4 bits forming the mantissa m and the last 2 bits
comprising the exponent e.  The m field is to be considered to be an
unsigned integer, while e is a 2s-complement signed integer.
(Thus negative floating-point numbers cannot be stored.)  
Make sure to verify for yourself that 
   
\begin{verbatim}
001110 + 010111 = 110110
\end{verbatim}

Note the design tradeoff here:  For a fixed overall storage size (6 bits
in the example above, 32 bits in most computers today) the more bits we
devote to the exponent, the wider the range of numbers we can store.
But the more bits I devote to the mantissa, the less roundoff error I
will have during computations.  Once I have decided on the string size
for my machine, the question of partitioning these bits into mantissa
and exponent sections then becomes one of balancing accuracy and range.

The floating-point representation commonly used on today's machines
is a standard of the Institute of Electrical and Electronic Engineers
(IEEE). It uses 32-bit storage and follows the same basic principles,
but has a couple of refinements to the simplest mantissa/exponent
format.  It consists of a Sign Bit, an 8-bit Exponent Field, and 23-bit
Mantissa Field.  (Here there is some distinction made between the terms
{\bf  mantissa} and {\bf  Mantissa Field}, and between {\bf  exponent} and
{\bf  Exponent Field}.

We will not go into further detail here, but the reader is urged to
think a bit of how this is implemented in hardware, say for an adder.

\subsection{Representing Character Data}

This is merely a matter of choosing which bit patterns will represent 
which characters.  The two most famous systems are the American 
Standard Code for Information Interchange (ASCII) and the Extended 
Binary Coded Decimal Information Code (EBCDIC).  ASCII stores each 
character as the base-2 form of a number between 0 and 127.  For 
example, `A' is stored as $65_{10}$ (01000001 = 0x41), `\%' as $37_{10}$ 
(00100101 =  0x25), and so on.  

A complete list of standard ASCII codes may be obtained by typing

\begin{verbatim}
man ascii
\end{verbatim}

on most Unix systems.  Note that even keys such as Carriage Return, 
Line Feed, and so on, are considered characters, and have ASCII codes.

Since ASCII codes are taken from numbers in the range 0 to 
$2^7 - 1 = 127$, each code consists of seven bits.  The EBCDIC system 
consists of eight bits, and thus can code 256 different characters, 
as opposed to ASCII's 128.  In either system, a character can be 
stored in one byte.  The vast majority of machines today use the
ASCII system.
  
What about characters in languages other than English?  Codings exist
for them too.  Consider for example Chinese.  Given that there are
tens of thousands of characters, far more than 256, two bytes are 
used for each Chinese character.  Since documents will often contain
both Chinese and English text, there needs to be a way to distinguish
the two.   Big5 and Guobiao, two of the most widely-used coding systems
used for Chinese, work as follows.  The first of the two bytes in
a Chinese character will have its most significant bit set to 1.
This distinguishes it from ASCII (English) characters, whose most
significant bits are 0s, in documents containing both English and
Chinese.  

The software which is being used to read (or write) a document, such
as {\bf celvis}, a Chinese version of the famous {\bf vi} text editor,
will inspect the high bit of a byte in the file.  If that bit is 0, then
the byte will be interpreted as an ASCII character; if it is 1, then
that byte and the one following it will be interpreted as a Chinese
character.

\subsection{Representing Machine Instructions}

Each computer type has a set of binary codes used to specify various
operations done by the computer's {\bf Central Processing Unit} (CPU).
For example, in the Intel CPU chip family, the code 0xc7070100, i.e. 

\begin{verbatim}
11000111000001110000000100000000,
\end{verbatim}

means to put the value 1 into a certain location of the computer's memory.
The circuitry in the computer is designed to recognize such patterns 
and act accordingly.  

Note that an instruction can get into the computer in one of two ways:

\begin{itemize}
\item [(a)]
We write a program in machine language (or assembly language, which 
is essentially the same), directly producing instructions such
as the one above.

\item [(b)]
We write a program in a high-level language (HLL) such as C, and the 
compiler translates that program into instructions like the one above.
\end{itemize}

Suppose for example we are using a PC running Linux, a PC version of
Unix, and that our source code is C language in files x.c and y.c.  
(The function main() and some declarations might be in x.c, while some
other functions called from main() are in y.c.)  If we issue the command

\begin{verbatim}
cc x.c y.c
\end{verbatim}

then first the compiler {\bf cc} will translate x.c and y.c into machine
language, creating files x.o and y.o.  (The letter `o' stands for {\bf
object}, a term used to describe machine-language files.)  Since PCs use
CPUs based on the Intel instruction set, these two files will contain
Intel machine language such as seen in the example above.  Another
system program named {\bf ld}, the {\bf linker}, will then link together
x.o and y.o into one combined executable machine-language file a.out.
(Though {\bf ld} can be run ``by hand'' from the Unix command line, here
it is invoked automatically by {\bf cc}.  The latter also removes x.o
and y.o after linking is completed.)

In some (relatively rare) cases, HLLs are either not efficient enough or
do not provide us direct access to certain needed hardware features, so
we must write in assembly language.  The suffix for assembly-language
files in Unix is .s, so the files we write in the illustration above
might be named u.s and v.s.  We might then apply the Unix assembler to
them, which is named {\bf as}:

\begin{verbatim}
as u.s v.s
\end{verbatim}

That would again produce files u.o and v.o, which would be linked
together by {\bf ld} to produce a.out.

You can also ask the compiler to produce a .s file from a .c file, 
using the -S command.  For example:

\begin{verbatim}
cc -S x.c y.c
\end{verbatim}

will produce x.s and y.s.  This is useful if you wish to write in
C but then ``tweak'' the code produced by the compiler for better
efficiency; after modifying the .s files by hand, you can then
run {\bf as} on them to produce your executable file.  The -S option
is also useful as a device to learn how the compiler stores HLL
variables, a subject to be covered later in this tutorial.



By the way, the reader should keep in mind that the assemblers and
compilers themselves are programs.  Thus they consist of machine
language instructions, though of course these instructions might have
themselves been generated from an HLL source too.

\subsection{It's the Software, Not to the Hardware}

A natural question to ask at this point would be how the computer 
``knows'' what kind of information is being stored in a given bit 
string.  For example, suppose we have the 16-bit string 
0111010000101011, i.e. in hex form 0x742b, on a machine using an 
Intel CPU chip in 16-bit mode.  Then
 
\begin{itemize}
\item [(a)]
if this string is being used to store a signed integer, then its 
value will be 29,739;

\item [(b)]
if this string is being used to store characters, then its contents 
will be the characters `t' and `+';
 
\item [(c)]
if this string is being used to store a machine instruction, then the 
instruction says to ``jump'' forward 43 bytes.
\end{itemize}

So, in this context the question raised above is, 

\begin{quote}
How does the computer ``know'' which of the above three kinds (or 
other kinds) of information is being stored in the bit string 0x742b?  
Is it 29,739?  Is it `t' and `+'?  Or is it a jump-ahead-43-bytes 
machine instruction?  
\end{quote}

The answer is, ``The computer does {\it not} know!''  As far as the 
computer is concerned, this is just a string of 16 0s and 1s, with 
{\it no} special meaning.  So, the responsibility rests with the 
person who writes the program---he or she must remember what kind of 
information he or she stored in that bit string.  If the programmer 
makes a mistake, the computer will not notice, and will carry out the 
programmer's instruction, no matter how ridiculous it is.  For example, 
suppose the programmer had stored {\it characters} in each of two bit 
strings, but forgets this and mistakenly thinks that he/she had 
stored {\it integers} in those strings.  If the programmer tells the 
computer to multiply those two ``numbers,'' the computer will 
dutifully obey!
  
As an example, consider the C library function {\bf printf()},
which is used to write the values of program variables to the screen.  
Suppose again that we have a variable Y of type {\bf int}, and
consider the C code

\begin{verbatim}
Y = -32697;
printf("%d %u %c\n",Y,Y,Y);
\end{verbatim}

again on a machine using an Intel CPU chip in 16-bit mode.  
We are printing the bit string in Y to the screen three times, but 
are directing that this bit string be interpreted first as a decimal 
signed integer (\%d); then as a decimal unsigned integer (\%u); then as
an ASCII character (\%c); and then go to a new line.  Here is the 
output that would appear on the screen:

\begin{verbatim}
-32697  32839  G
\end{verbatim}

The bit string in Y is 0x8047.  Interpreted as a 16-bit 2's complement
number, this string represents the number -32,697.  Interpreted as
an unsigned number, this string represents 32,839.  If the least
significant 8 bits of this string are interpreted as an ASCII 
character, they represent the character `G'.

But remember, the key point is that the {\it hardware} is ignorant; 
it has no idea as to what type of data we intended to be stored in 
Y's memory location.  The interpretation of data types was solely in 
the software.  As far as the hardware is concerned, the contents of a 
memory location is just a bit string, nothing more.  

In fact, we can view that bit string without interpretation as some 
data type, by using the \%x format in the call to {\bf printf()}.  This 
will result in the bit string itself being printed out (in hex notation).

This idea of ``who is responsible for what?''---e.g. asking whether a 
particular concept is in the domain of hardware versus software---will 
be one of the themes of this book.

Let us illustrate this with one more point on the example above.
The machine instructions within the compiled form of {\bf printf()}
will print out the character string ``32697'' to the screen.
In other words, those instructions will first send 0x33, the ASCII 
code for the character `3', to the screen, then send 0x32 for `2', 
and so on.  It is easy to take this for granted, but there is quite
a bit involved here.

First of all, keep in mind the vast difference between the
{\it number} 32697 and the {\it character string} ``32697''.
It is the former which is stored in Y, as 0x7fb9, i.e.

\begin{verbatim}
111111110111001
\end{verbatim}

(Verify this!)  In order to convert this to the characters `3',
`2', `6', `9' and `7', the code in {\bf printf()} must do repeated
division:  It first divides by 10,000, yielding 3 with a remainder
of 2,697.  The 3, i.e. 11, is changed to `3', i.e. the ASCII 00110011.
The 2,697 is then divided by 1,000, yielding 2 with a remainder of
697.  The 2 is converted to `2', i.e. 00110010, and so on.  (We will
then divide by 100 and 10.)

The second question is, how will these characters then be displayed 
on the screen?

You may already know that a computer monitor consists of many dots
called {\bf pixels}.  There may be, for instance, 1028 rows of 768
pixels per row.  Any image, including characters, are formed from
these pixels.  On a nongraphics screen (often called a {\bf dumb
ASCII terminal}), the hardware directly forms the dots for whichever 
character it receives from the computer.  In our example above, for 
instance, the computer sends 0x33 along the cable from the computer 
to the screen, and the screen then forms the proper dots to draw
the character `3', called the {\bf font} for `3'.

By contrast, on a graphics screen, software plays the role of the
middleman.  For concreteness, consider an {\bf xterm} window on
Unix systems.  (You need not have used {\bf xterm} to follow this
discussion.  If you have used Microsoft Windows, you can relate
the discussion to that context if you wish.)  The {\bf  printf()} call 
we saw above will send the value 0x33 not directly to the screen, but 
rather to the {\bf xterm} program.  The latter will look up the font 
for `3' and then send it to the screen, and the screen hardware then 
displays it.

We get much more flexibility this way.  For one thing, upon starting 
up an {\bf xterm} window, the user can specify fonts; a middle-aged
user who is starting to have trouble reading small print can specify
larger fonts, for instance.  Another very powerful dividend of this
flexibility is that the user can specify foreign-language fonts,
and thus be able to read and write e-mail in, say, Chinese.

\section{Main Memory Organization}

During the time a program is executing, both the program's data and 
the program itself, i.e. the machine instructions, are stored in main
memory.  In this section, we will introduce main memory structure.
(We will usually refer to main memory as simply ``memory.'')

\subsection{Bytes, Words and Addresses}

Memory can be viewed as a long string of consecutive bytes.  Each
byte has an identification number, called an {\bf address}.  Again, 
an address is just an ``i.d. number," like a Social Security Number 
identifies a person, a license number identifies a car, and an 
account number identifies a bank account.  Byte addresses are 
consecutive integers, so that the memory consists of Byte 0, Byte 1, 
Byte 2, and so on.
  
On each machine, a certain number of consecutive bytes is called a 
{\bf word}.  The number of bytes or bits (there are eight times as 
many bits as bytes, since a byte consists of eight bits) in a word in 
a given machine is called the machine's {\bf word size}.  This is 
usually defined in terms of the size of number which the CPU addition 
circuitry can handle, which for most machines today is 32 bits.
In other words, the CPU's adder inputs two 32-bit numbers, and
outputs a 32-bit sum.

Most MIPS, SPARC and other CPUs popular today have 32-bit words.
Early members of the Intel CPU family had 16-bit words, while the
later ones were extended to their current 32-bit size.   In order to 
ensure that programs written for the early chips would run on the 
later ones, Intel designed the later CPUs to be capable of running in 
two modes, one with 16-bit words and the other being a 32-bit mode.

Since working with 32-bit strings is cumbersome for us humans, many
of our examples here will be for 16-bit words.

\subsection{Interactions Between the CPU and Memory}

The Central Processing Unit (CPU) is where all the ``action''
takes place, i.e. where a program gets executed.  The CPU consists
of {\bf registers}, for temporary storage of data, and the
{\bf arithmetic and logic unit} (ALU), where the actual
computation (e.g. addition and subtraction) takes place.  A
special register, the {\bf program counter} (PC) indicates
where in memory the currently-executing instruction is stored.

The CPU and memory are connected by a {\bf bus}, which consists of sets
of lines for address, data and control.

For example, consider the Intel assembly-language instruction

\begin{verbatim}
MOV AX,[200]
\end{verbatim}

which copies a data item from location 200 in memory to AX, one of the
registers.  Say this instruction (in its machine-language binary form)
is stored in location 5204 of memory.  Here is what will occur when
this instruction is executed :

\begin{itemize}

\item [(a)] Since the PC contains 5204, the CPU needs to fetch the
instruction from word 5204 in memory.  Thus the CPU will put 5204 onto
the address lines in the bus, and assert the Read line in the control
portion of the bus.  

\item [(b)] The memory will send the instruction to the CPU on the
data lines.

\item [(c)] The CPU decodes the instruction, finding that it is a
MOV (``copy'') operation with the second operand being in memory
location 200.

\item [(d)] The CPU needs to read word 200 in memory, so the CPU
puts 200 on the address lines and asserts the Read line.

\item [(e)] Say the contents of workd 200 is 12.  The memory puts
12 on the data lines. 

\item [(f)] The CPU receives the 12 and puts it in AX.
\end{itemize}

\subsection{Storage of Variables in HLL Programs}
\label{store}

When you execute a program, both its instructions and its data are 
stored in memory.  Keep in mind, the word {\bf  instructions} here 
means machine language instructions.  Again, these machine language 
instructions were either written by the programmer directly, or they 
were produced by a compiler from a source file written by the 
programmer in C or some other HLL.  Let us now look at the storage of 
the {\it data} in the C/HLL case.

\subsubsection{Variable Names Versus Memory Addresses:  Introduction}

In an HLL program, we specify our data via names.  The compiler will 
assign each variable a location in memory.  Generally (but not always, 
depending on the compiler), these locations will be consecutive.

C compilers tend to store local variables in the reverse of the order 
in which they are declared.  For example, consider the following program:

\begin{verbatim}
PrintAddr(VarName,Addr)
   char VarName[]; int Addr;

{  printf("the address of %s is %x\n",VarName,Addr);  }

main()

{  int X,Y,W[4];
   char U,V;

   PrintAddr("X",&X);
   PrintAddr("Y",&Y);
   PrintAddr("W[3]",&W[3]);
   PrintAddr("W[0]",&W[0]);
   PrintAddr("U",&U);
   PrintAddr("V",&V);

}
\end{verbatim}

I ran this on a Pentium machine running the Linux operating system,
which runs in 32-bit mode.  The output of the program was

\begin{verbatim}
the address of X is bffffb84
the address of Y is bffffb80
the address of W[3] is bffffb7c
the address of W[0] is bffffb70
the address of U is bffffb6f
the address of V is bffffb6e
\end{verbatim}

On the other hand, there is wide variation among C compilers as to
how they store global variables.

Virtually all C compilers store variables of type {\bf int} in one word,
as we have seen above, and we will assume this from now on unless
otherwise stated.  The same is true for variables of type {\bf float},
as long as the word size is 32 bits, the size of the IEEE floating-point
standard; for 16-bit machines, this means that {\bf float} variables
must be stored in a pair of words.  

Note once again that the hardware is quite unaware of the data
type of an HLL variable.  As far as the hardware is concerned, each
variable is simply a bit string.  For example, suppose in a C program
we have the declaration

\begin{verbatim}
char C;
\end{verbatim}

and the statement

\begin{verbatim}
C = 65;
\end{verbatim}

We are assigning a value of type {\bf int} to a variable of type {\bf 
char}.  But the C language allows this, and since the hardware does 
not know about data types anyway, the hardware will not ``complain'' 
either.  

The Microsoft C compiler on an Intel machine running in 16-bit mode 
will translate this statement to the machine instruction

\begin{verbatim}
1100011000000110111000000000000101000001
\end{verbatim}

Note the last eight bits here, 01000001; they are the binary 
representation of the number 65.  If the instruction had instead been

\begin{verbatim}
C = 'A';
\end{verbatim}

then the compiler would have produced {\it exactly the same machine 
instruction}, since the ASCII code for `A' is again 01000001.
The instruction itself says to copy this bit string, 01000001,
to the memory byte allocated to the variable C.  

When you compile a program from an HLL source file, the compiler first 
assigns memory locations for each declared variable.\footnote{These
locations will not actually be used at that time.  They will only be
used later, when the program is actually run.}  For its own reference
purposes, the compiler will set up a {\bf symbol table} which shows
which addresses the variables are assigned to.  However, it is
very important to note is that {\it the variable names in a C or 
other HLL program are just for the convenience of us humans.}  In the 
machine language program produced from our HLL file by the compiler, 
all references to the variables are through their addresses in memory, 
with no references whatsoever to the original variables names.  Those 
names are discarded when the compiler finishes its work.

For example, suppose we have the statement 

\begin{verbatim}
X = Y + 4;
\end{verbatim}

When the compiler produces some machine-language instructions to
implement this action, the key point is that these instructions
will {\it not} refer to X and Y.  Say X and Y are stored in Words
504 and 1712, respectively.  Then the machine instructions the
compiler generates from the above statement will only refer to Words
504 and 1712, the locations which the compiler chose for the
C variables X and Y.

For instance, the compiler might produce the following sequence of 
three machine language instructions:

\begin{verbatim}
copy Word 1712 to a register in the CPU
add 4 to the contents of that register
copy that register to Word 504
\end{verbatim}

There is no mention of X and Y at all!  The names X and Y were just
{\it temporary} entities, for communication between you and the
compiler.  The compiler chose locations for each variable, and
then translated all of your C references to those variables
to references to those memory locations, as you see here.  Again,
when the compiler is done compiling your program, it will simply
discard the symbol table entirely.  If say on a Unix system you type

\begin{verbatim}
cc x.c
\end{verbatim}

which creates the executable file a.out, that file will not
contain the symbol table.

There is one exception to this, though, which occurs when you are
debugging a program, using a debugging tool such as {\bf gdb},
{\bf dbx} or {\bf ups}.\footnote{You should \underline{always}
use a debugging tool when you are debugging a program.  {\it Don't
debug by just inserting a lot of {\bf printf()} calls!}  Use of
a debugging tool will save you large amounts of time and effort.
Professional software engineers use debugging tools as a matter
of course.}  Within the debugging tool you will want to be able
to refer to variables by name, rather than by memory location,
so in this case you do need to tell the compiler to retain the
symbol table in a.out.  You do so with the -g option, i.e.

\begin{verbatim}
cc -g x.c
\end{verbatim}

\subsubsection{Array Variables}

As seen in an example above, array variables are generally 
implemented by compilers as contiguous blocks of memory.  For example, 
the array declared as

\begin{verbatim}
int X[100];
\end{verbatim}

would be allocated to some set of 100 consecutive words in memory.
If X is a local variable, X[0] will be the last of these 100
consecutive words, and X[99] will be the first.

What about two-dimensional arrays?  For example, consider the 
four-row, six-column array 

\begin{verbatim}
int G[4][6];
\end{verbatim}

Again, this array will be implemented in a block of consecutive
words of memory, more specifically 24 consecutive words, since these
arrays here consist of $4\times6 = 24$ elements.  But in what order 
will those 24 elements be arranged?  Most compilers use either
{\bf row-major} or {\bf column-major} ordering.  To illustrate this,
let us assume for the moment that this is a global array and that
the compiler stores in non-reverse order, i.e. G[0][0] first and
G[3][5] last.  

In row-major order, all elements of the first row are stored at the 
beginning of the block, then all the elements of the second row are 
stored, then the third row, and so on.  In column-major order, it is 
just the opposite:  All of the first column is stored first, then all 
of the second column, and so on.

In the example above, consider G[1][4].  With  row-major order, this 
element would be stored as the 11th word in the block of words 
allocated to G.  If column-major order were used, the it would be 
stored in the 18th word.  (The reader should verify both of these 
statements, to make sure to understand the concept.)  

C compilers use the row-major system.  However, as mentioned earlier, 
for local variables they store variables in reverse.  In the example
above, G[3][5] would be first and G[0][0] last.  The reader should
verify that G[1][4] would be the 14th word in the block.

\subsubsection{Struct and Pointer Variables}

Advanced data types are handled similarly, again in contiguous
memory locations.  For instance, consider the 
{\bf struct} type in C, say

\begin{verbatim}
struct S {
   int X;
   char A,B;
};
\end{verbatim}

would on a 16-bit machine be stored in four consecutive bytes, first
two for X and then one each for A and B.  On a 32-bit machine, it would
be stored in six consecutive bytes, since X would take up a word and
thus four bytes instead of two.  

Note, though, that most compilers will store complex objects like this
to be {\bf aligned on word boundaries}.  Consider the above {\bf struct}
S on a 32-bit machine, and suppose we have the local declaration

\begin{verbatim}
struct S U,V;
\end{verbatim}

U and V collectively occupy 12 bytes, thus seemingly three words.  But
most compilers will refuse to start an instance of S in the middle of
a word.  Thus although A and B will be stored contiguously in the sense
that no other variables will be stored between them, they will be stored
in four consecutive words, not three, with their addresses differing
by 8, not 6.  There will be two bytes of unused space between them.

The {\bf *} operator in C is one of the reasons for C's popularity.
This way, a programmer can access specific words in memory from a 
high-level language program, instead of having to resort to 
machine/assembly language.  

{\it A pointer is an address.}  In C, for example, suppose we have 
the declaration

\begin{verbatim}
int *P,X;
\end{verbatim}

We are telling the compiler to allocate memory for two variables,
one named P and the other named X.  We are also telling the compiler
what types these variables will have:  X will be of integer type,
while the * says that P will be of pointer-to-integer type---meaning
that P will store the address of some integer.  For instance, in our
program, we might have the statement

\begin{verbatim}  
P = &X;
\end{verbatim}

which would place the address of X in P.  (More precisely, we should
define this as the lowest-address byte of X.) If one then executed the
statement

\begin{verbatim}
printf("%x\n",P);
\end{verbatim}

the address of X would be printed.

Another aspect of C pointers which explicitly exposes the
nature of storage of program objects in memory is {\bf pointer
arithmetic}.  For example, suppose P is of pointer type.
Then P+1, for example, points to the next consecutive object
of the type to which P points.  If for instance we have the 
declaration

\begin{verbatim}
float A,B,C,*Q;
\end{verbatim}

and we execute the statement

\begin{verbatim}
Q = &B;
\end{verbatim}

Then Q+1 points to A, if A and B are stored contiguously and in
``reverse'' order.

Note by the way that in the {\bf float} declaration above, Q may be
stored contiguously with A, B and C, even though it is a pointer 
variable.  Q will have the lowest address, followed by C, then B,
then A.  In fact, if we execute the statement

\begin{verbatim}
Q = &B;
\end{verbatim}

then Q-2 will point to Q!

\subsubsection{Stack Frames}

In most modern machine/compiler combinations, function calls are 
handled via the stack.  Not only does a machine CALL instruction save
the return program counter value on the stack, but also the compiler
produces code to push function parameters on the stack, and also to
allocate stack space for local variables in the called function.

For example, suppose we have a C function whose first few lines are

\begin{verbatim}
x(a,b)
   int a,b;

{  int c,d,e;
\end{verbatim}

and that there is a call to the function like this:

\begin{verbatim}
x(m,n);
\end{verbatim}

the compiler will translate the call to something like

\begin{verbatim}
PUSH N
PUSH M
CALL X
\end{verbatim}

(I am assuming a ``generic'' machine here, e.g. with a PUSH instruction,
but equivalent would be generated on any machine), and will translate
the beginning of the function itself to something like

\begin{verbatim}
SUB SP,3
\end{verbatim}

(assuming successive words differ in address by 1, and assuming that the
stack grows toward 0), in order to allocate three words on the stack 
for x's local variables c, d and e.

In other words, for a given function call, the portion of the stack will
be devoted to that call will look like this:

\begin{verbatim}
local variables
return address (1 word past the point where the call was made)
parameters
\end{verbatim}

This is called the {\bf stack frame} for that call.

\end{document} 



