\chapter{Overview on endianness}
\label{cha:endianness-overview}

The MOVE framework historically ran on big-endian platforms like HPPA,
Sparc and MIPS. With the increased popularity of Linux running on
relatively cheap little-endian platforms, like the x86 platform, the
need for a port of the MOVE framework to a little-endian host platform 
arose. At the same time, the ``PcomP'' implementation of the MOVE
architecture was decided to be little-endian. This and the next
chapter will deal with changing the MOVE framework to be running
independent of the host platform's endianness, as well as changing the 
MOVE framework to be able to generate and simulate code for both
little and big-endian targets.

This chapter will give an overview on endianness dependence itself,
and how that affects implementation of tools, with the emphasis on
emulation tools. Chapter~\ref{cha:endianness-impl} will discuss how
the principles of this chapter are used in the port of the MOVE
framework.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Endianness in general}
\label{sec:end-overview}

Endianness, deals with the ordering of fields within an item. Usually
it means byte ordering within a halfword, word and double
word. However it can also mean bit ordering within bytes. Byte
ordering is the most visual, since most memory systems are byte
addressable, IO works on bytes, strings are packed as bytes within
words, etc. Bit ordering comes into play when structures are accessed
with bitfields in a byte. The latter becomes architecturally visible
when a program accesses bitfields within a byte.

The historical name ``endianness'' refers to the book ``Gulliver's
travel'' by Jonathan Swift. The Lilliputians liked to break their eggs 
on the small end and the Blefuscudians on the big end. According to
the book, {\em ...It is computed that eleven Thousand Persons have, at 
several Times, suffered Death, rather than submit to break their Eggs
at the smaller End. Many hundred large Volumes have been published
upon this Controversy}. The analogy is taken very well, since there is 
no real ``correct'' implementation. Both have their advantages and
disadvantages. 

The official definition of big-endian and little-endian is the
following:\\
\\
{\bf big endian} ordering means  storing the least significant byte at 
the most significant address.\\
\\
{\bf little endian} ordering means storing the least significant byte
at the least significant address.\\
\\
Consider the following 16 bytes of data in table~\ref{tab:end-mem}

\begin{table}[htb]
\begin{center}
\small
\begin{tabular}{|r|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
{\bf address}  & 00 & 01 & 02 & 03 & 04 & 05 & 06 & 07
               & 08 & 09 & 10 & 11 & 12 & 13 & 14 & 15\\
\hline
{\bf contents} & 00 & 01 & 02 & 03 & 04 & 05 & 06 & 07
               & 08 & 09 & 10 & 11 & 12 & 13 & 14 & 15\\
\hline
\end{tabular}
\end{center}
\caption{Memory as an array of bytes}
\label{tab:end-mem}
\end{table}

If instead of considering the memory as an array of bytes, we consider 
the same memory contents as four 32-bit words. Then it will be shown
that a little or a big endian machine have a different view on the
memory. Table~\ref{tab:end-little} will show a little-endian memory
and table~\ref{tab:end-big} will show a big-endian memory.

\begin{table}[htb]
\begin{center}
\small
\begin{tabular}{|c|c|c|c|c|}
\hline
\multicolumn{4}{|c|}{\bf contents}&{\bf word addr}\\
\hline
03 & 02 & 01 & 00 & {\bf 00}\\
07 & 06 & 05 & 04 & {\bf 04}\\
11 & 10 & 09 & 08 & {\bf 08}\\
15 & 14 & 13 & 12 & {\bf 12}\\
\hline
\end{tabular}
\end{center}
\caption{Little endian memory as an array of words}
\label{tab:end-little}
\end{table}


\begin{table}[htb]
\begin{center}
\small
\begin{tabular}{|c|c|c|c|c|}
\hline
{\bf word addr} & \multicolumn{4}{|c|}{\bf contents}\\
\hline
{\bf 00} & 00 & 01 & 02 & 03\\
{\bf 04} & 04 & 05 & 06 & 07\\
{\bf 08} & 08 & 09 & 10 & 11\\
{\bf 12} & 12 & 13 & 14 & 15\\
\hline
\end{tabular}
\end{center}
\caption{Big endian memory as an array of words}
\label{tab:end-big}
\end{table}

In the two tables, the bytes are grouped into four byte words, which
are shown in the normal Arabic form, with the most significant byte on 
the left. In table~\ref{tab:end-little} the word address column was
put on the right (``little end'') because the computer uses the
address of the least significant byte, the byte on the right, to
address the word. In table~\ref{tab:end-big}, the address column is on 
the left (``big-end''), showing that the computer addresses the most
significant byte in words operations. As a result, a little endian
processor loading the 32-bit work at word address {\tt 0x00} would
obtain the value {\tt 0x03020100}, while a big endian processor would
obtain the value {\tt 0x00010203}.


An important observation that has to be made is that if a certain
machine is unable to access bits in a byte, the endianness with
respect to bit-ordering means nothing. This is because the program has
no way to access data smaller than a byte anyway, and as long as the
machine stores and retrieves the data in a consistent way, it doesn't
matter how exactly this is done. The same goes for a machine
which is word-addressable, because words will always be fetched as a
whole from memory, and it doesn't matter how those words are stored in memory.

Examples of little-endian machines are the Intel x86 family and various
architectures from DEC, like the VAX, the PDP-11 and the
Alpha. Examples of big-endian machines are the Sun Sparc, HPPA and the
m68k architecture. Still other architectures, like the PowerPC, the
MIPS and the Intel IA-64 architecture, are capable of operating in
either big or little endian mode. Usually the operating system
dictates the endianness that the processor is going to use during that 
boot. 

Regarding endianness, we can divide the problem in two parts. First is 
the most known one, the so-called ``host endianness''. This kind of
endianness concerns the problem of begin able to use data between
platforms of different endianness. What one wants to do is, for
instance, write a binary file on a big-endian platform, and read it on 
a little-endian platform. This is what section~\ref{sec:host-end}
discusses.
Section~\ref{sec:target-end} discusses another problem regarding
endianness, the so-called target-endianness. This kind of endianness
concerns the fact that a certain host should be able to process data
in a certain endianness, without having that data being related to the 
host itself. This is a common scenario when dealing with foreign
binaries. MOVE specific, this means that a certain host has to be able 
to process binaries, and simulate binaries, from any endianness.
First we will present some solutions to handle endianness, both on the 
software level as on the hardware level.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Solutions}
\label{sec:end-solutions}




\subsection{Software solutions}
\label{ssec:soft-solution}

There are different ways to agree on an interface:
\begin{compactenumerate}
\item {\bf Form an endianness-independent transport layer.} Certain graphics 
applications, like Framemaker, have an option to write the data to an
endianness independent file. With Framemaker, this is the
{\tt.mif}-format, or Maker Independent Format. This file can be read
on any platform, but is two to three times larger than the normal
{\tt.doc} format that Framemaker uses. Sun has its XDR (eXternal Data
Representation) format~\cite{end-sol}, which, apart from endianness
independence, also claims independence from various floating point
implementations.
\item {\bf Let the data be stored/transmitted in the native endianness of
the sender.} This is done along with tag or header that indicates endianness. This
method is deployed by the TIFF graphics format, which can either be
``IBM ordered'' or ``Macintosh ordered''. A header specifies whether
the data is big (``Macintosh ordered'') or little (``IBM ordered)
endian. Another scenario where this principle is applicable is when
dealing with binaries from a different architecture. If a binary is in 
a certain endianness, and it is emulated or simulated on a host
machine, this host machine has to check for endianness in that
'target' architecture and handle accordingly.
\item {\bf Let the data always be a certain kind of endianness.} This
is the most common way to handle endianness, since it is unambiguous
what the data's endianness is. This way a program only has to take
into account its own endianness.
This is also the way the Internet works. Data transmitted over the
internet is always big-endian, and Unix systems provide the system
calls {\tt ntohl(3)} and {\tt htonl(3)}, for respectively
``network-to-host'' swapping and ``host-to-network'' swapping.
\end{compactenumerate}

\subsection{Changing and detecting endianness}
\label{ssec:end-detect}

To ``encode'' an endianness independent layer, like in option 1, every 
designer is free to choose his own implementation. Option 2 and 3 only 
need a so-called ``byte-swap'' or ``byte-reordering''. For this
``byte-swap'', a very simple piece of code can be used:

{\small
\begin{verbatim}
#define BSWAP32(x) \
  x = ((((x) & 0xff000000) >> 24) | (((x) & 0x00ff0000) >>  8) | \
      (((x) & 0x0000ff00) <<  8) | (((x) & 0x000000ff) << 24))
\end{verbatim}
}%small

What we do here is just swapping bytes 1 and 4, and bytes 2 and 3 in a 
word. This will indeed swap the data, and will convert
tables~\ref{tab:end-little}~and~\ref{tab:end-big} into each other.
This macro is exactly the code used in the  {\tt ntohl(3)}
and {\tt htonl(3)} calls on little-endian platforms. On big-endian
platforms, where there is no swap needed, since host ordering and
network ordering are the same, these two calls are null-macros, a very 
efficient way to implement a no-operation in C or C++.

A good way to detect the endianness of a platform is the following
standard piece of code:

{\small
\begin{verbatim}
long i = 0x44332211;
unsigned char* a = (unsigned char*) &i;
end = (*a != 0x11); 
printf("The endianess is %s!\n", ((end==1)?"big":"little"));
\end{verbatim}
}%small

This piece of code will fetch one byte out of the word {\tt i}, by getting
the byte addressed by the pointer to {\tt i}. If the platform's endianness
is little, the byte {\tt 0x11} is fetched, since the {\em least} significant
byte is stored at the most significant address, which is the pointer's
address. If the platform's endianness is big, the byte {\tt 0x44} is
fetched, since the {\em most} significant byte is stored at the most
significant address. And the most significant address is the address to
which the pointers {\tt i} and {\tt a} point.


\subsection{Hardware solutions}

Although not in the scope of this thesis, a brief overview on hardware 
solutions to the endianness problem are discussed. If there is no way
to have software do byte-swapping, the hardware has to do this. A
common principle to do this is to give the system multiple views on
the address space where the endianness-dependent devices, like memory
or graphics processor, reside. These various views are called 
{\em apertures}. For example, a PCI based  graphics adapter that
internally uses a little endian processor can provide two apertures
(ranges of addresses) for its frame buffer. Accesses to the little
endian aperture store the data as presented on the bus directly into
the frame buffer; accesses to the big endian aperture swaps the data
bytes before storing them. Thus, an application running on a big
endian processor can simply access the big endian aperture and store its 
big endian data just as if it were running on a little endian
processor. The device takes care of swapping the data in hardware as
necessary. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Host endianness}
\label{sec:host-end}

Host endianness concerns the way data can be kept portable across
platforms. This section will concentrate mainly on files, although its 
principles can easily be extended to other forms of
interoperatibility, like shared memory between a graphics processor
and a CPU, or inter-architecture buses (PCI, SCSI). 
Regarding Move, this means that solution 3 from
section~\ref{ssec:soft-solution} is used: Let the data on disk always
have the same endianness. This way the only check a program has to do
is its own endianness.

\subsection{Example}

As an example of host-endianness, we will explain the profiling code
in the scheduler. The profiles, including frequency counts and memory
dependencies, are target-independent data. Therefore, they are stored
on disk in a pre-defined endianness. In this case this is big-endian.

The functions {\tt Prog::SaveProfile} and {\tt Prog::LoadProfile} are
responsible for writing and reading the profiles. Therefore the
following code can be found:

{\small
\begin{verbatim}
for(p = proc; p; p++)
{
  for(b = p->blck; b; b++)
  {
#if HOST_LITTLE_ENDIAN
    f = SwapEndianess(b->freq);
#else
    f = b->freq;
#endif
    file.write((char *) &f, sizeof(double));
  }
}
\end{verbatim}
}

For each procedure, and each block in that procedure, an integer {\tt
b->freq} exists, indicating the frequency of that basic block during
execution. Because agreed was that all data on disk was big endian, a
byte swap is performed, governed by the predefine {\tt
HOST\_LITTLE\_ENDIAN}. The function {\tt SwapEndianess} performs the
actual byte swap in the word {\tt b->freq}.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Target endianness}
\label{sec:target-end}

Target endianness concerns the portability of foreign code on a
platform of random endianness. This is especially relevant here, since
any platform, either big or little, should be able to omit, schedule
and simulate binaries from any MOVE architecture. Now it is, contrary
to host-endianness, important to keep the endianness of a file intact
while reading and writing. This means we take on option 2 as presented
in the list of subsection~\ref{ssec:soft-solution}.  This option says
that the endianness of a certain file can depend. This means that the
program has to know up front what kind of file it is dealing
with. Regarding Move, this means that the tools have to know what kind
of endianness the target-binary has.  Since the host-endianness still
has to be taken into account, the rules for swapping get more
complicated. Table~\ref{tab:end-swap} shows all cross-combinations
possible.  For swapping, the macro as presented in
subsection~\ref{ssec:end-detect} can be used.


\begin{table}[htb]
\begin{center}
\small
\begin{tabular}{|c|c|c|}
\hline
{} & {\bf target} & {\bf target} \\ {} & {\bf big} & {\bf little} \\
\hline
{\bf host big} &         no swap         &   swap       \\
{\bf host little} &      swap            &   no swap    \\
\hline
\end{tabular}
\end{center}
\caption{Endianness swap depending on host and target}
\label{tab:end-swap}
\end{table}


\subsection{Example}
As an example of target endianness, we take the reading of the
text segment of the serial binary. The text segment is
``target-dependent'', that means that the serial binary can contain
either Move code for a little-endian Move architecture or a big-endian 
Move architecture. The scheduler is compiled with an option that
indicates what kind of target-endianness is should be capable of
handling.
This is defined in the {\tt config.h} file of the scheduler:

{\small
\begin{verbatim}
#define __pcomp__

#ifdef __pcomp__
  #define TARGET_LITTLE_ENDIAN              1
  #define TARGET_BIT_FIELDS_LEFT_TO_RIGHT   0
#else
  #define TARGET_LITTLE_ENDIAN              0
  #define TARGET_BIT_FIELDS_LEFT_TO_RIGHT   1
#endif
\end{verbatim}
}

By setting the {\tt \_\_pcomp\_\_} define, the target-endianness is known
throughout the whole scheduler. Then we add some extra defines that
indicate whether the target-endianness is different from the
host-endianness (remember that the host-endianness is already stated
in the {\tt HOST\_LITTLE\_ENDIAN} defines, derived from the presence
of the compiler-required defines {\tt \_\_386} and {\tt \_\_sun}.

{\small
\begin{verbatim}
#if    HOST_LITTLE_ENDIAN && TARGET_LITTLE_ENDIAN
  #define SWAP_ENDIANESS 0
#elif  HOST_LITTLE_ENDIAN && !TARGET_LITTLE_ENDIAN
  #define SWAP_ENDIANESS 1
#elif !HOST_LITTLE_ENDIAN && TARGET_LITTLE_ENDIAN
  #define SWAP_ENDIANESS 1
#elif !HOST_LITTLE_ENDIAN && !TARGET_LITTLE_ENDIAN
  #define SWAP_ENDIANESS 0
#endif
\end{verbatim}
}

Now we can proceed to the file {\tt exec.h}, which implements the {\tt
AOut} class that reads in the serial binary.  Now we can read in the
whole text segment.  class {\tt AoutMove} represents a move
instruction in the binary.

{\small
\begin{verbatim}
AoutMove* text = (AoutMove *) &image[N_TXTOFF(*exec)];
#if SWAP_ENDIANESS
  SwapEndianess(text, exec->a_text);
#endif
\end{verbatim}
}

We simply map the whole binary (represented by {\tt image}) to the
{\tt text} array. Now the only thing left to change is the ordering of
the bytes in a word. Since this ordering is dependent on both the host
ordering as the target ordering, the {\tt SWAP\_ENDIANESS} define
governs whether a swap is needed, pursuant to
table~\ref{tab:end-swap}.
