Alignment and Ordering Issues

This handout will explain alignment and byte-ordering issues -- topics which are ignored by the book but can make an important impact on the way programs run.
"Memory alignment" is a term which refers to where a multi-byte variable is stored in a computer with a 16-bit or larger data path to memory. In the following discussion, we assume that we have a computer with a 16-bit (2 byte) wide path to memory (such as an 8086, 80286, or 80386sx). In such a computer, the following picture represents what the first few memory locations look like, where each box represents a byte of memory, and the numbers are the memory addresses:
Each row in this figure represents the 16 bits that can be transferred from the memory to the CPU when data is requested, or to the memory when data is saved. The way that the hardware is set up, any request to memory can involve only one row in the table. It‘s easy to see that if the CPU wants to get the byte stored at address 3, it‘s no problem -- it simply brings in the 16 bits that contain bytes 2 and 3, and extracts the correct byte. The same is true for any single byte, stored anywhere in memory.
However, when a two-byte word is requested, the story changes a bit. The address of a word is the address of the first byte in the word, so the word at address 4 is really made up of two bytes: byte 4 and byte 5 (the darkened box in the picture). In this example, it‘s again no problem to read this word from memory -- the CPU simply requests the 16 bits starting at address 4.
The problem comes when the program requests the word stored at address 5 (or any other odd address). In this case, the desired word is made up of bytes 5 and 6, and since they aren‘t in the same row in our picture, we can‘t simply request that word from memory. The CPU will translate such a request from a program into two memory requests: one for the word made up of bytes 4 and 5, and one for the word made up of bytes 6 and 7. The CPU can then extract bytes 5 and 6 from these two words, and put these two bytes together in order to create the word of data that was requested. Notice that this entire discussion could be repeated with larger data sizes -- if we were using a computer with a 32-bit wide data path to memory, then we could look at the problem of accessing a 32-bit variable that spanned across two 32-bit pieces of memory. With that in mind, we next define what is meant by an "aligned access" and an "unaligned access."
The first example that we considered, where the word at address 4 was requested, is an example of an aligned access, whereas the second access is an example of an unaligned access. More generally, if you are accessing an n-byte piece of data, the beginning address must be a multiple of n in order for the access to be aligned. All other accesses are unaligned accesses. Since we were talking about 2-byte pieces of data (words), aligned accesses are those that are at even addresses. On a 32-bit computer, all 32-bit data must be stored at an address that is a multiple of 4 in order to be aligned. Notice that as a special case of this definition, accessing one byte of data is always an aligned access.
Alignment is important because, as explained above, an unaligned read access can take twice as long as an aligned access. In fact, on many of the newer processors, such as the Sun SPARC and the DEC Alpha, there is no hardware to handle unaligned accesses! This means that such accesses must be handled by software, which can be over 10 times slower than an aligned access. Furthermore, when you declare a word variable in assembly language, the assembler puts that word at the next available address, making absolutely no distinction between aligned and unaligned data. Fortunately there is an easy way to fix this.
To make sure that data is aligned, there is a special assembler directive ALIGN. To use this directive to make sure a piece of data is aligned, simply place "ALIGN n" on a line immediately before the data you want aligned, where you replace n with the size of the data you want aligned. The ALIGN statement will add enough "padding" so that the following data begins at a multiple of n. The following example shows data segment declarations for variables of different sizes -- in the first example, the multi-byte data may or may not be aligned, so you may suffer a performance penalty. In the second example, the ALIGN instruction is used to guarantee that the multi-byte variables are aligned.
Possibly Unaligned .DATABVAR DB 4NROWS DW 25NCOLS DW 80CRET DB 13LADDR DD ?Alignment Guaranteed .DATABVAR DB 4ALIGN 2NROWS DW 25NCOLS DW 80CRET DB 13ALIGN 4LADDR DD ?
What we‘ve seen in this section is that as far as efficiency goes, all words are not equal. While high-level languages usually take care of alignment issues for the programmer, assembly language provides no such "help" unless it is explicitly asked for by the programmer. Therefore, alignment needs to be kept in mind when writing assembly language programs.
Another issue that comes up when accessing a multi-byte piece of data is called "byte ordering" (or sometimes called the "byte sex" of a machine). In particular, consider a 16-bit word of data, 1234h, that is stored in memory. This word consists of two bytes: 12h, called the "Most Significant Byte" (or MSB), and 34h, called the "Least Significant Byte" (or LSB). If this word were to be stored at address 4, then as we have just seen the bytes will be stored in memory locations 4 and 5. The question is, which byte goes where?
There are two options for a 16-bit word: Little Endian: On a little endian machine, the LSB (the "little end") is stored in the first byte. So in the example above, 34h would be stored in byte 4 and 12h would be stored in byte 5. The Intel x86 family of processors that are used in PC compatible computers are all little endian, as is the Vax line of computers build by Digital Equipment Corporation. Big Endian: On a big endian machine, the MSB is stored first. In this example above, this translates into 12h being stored in location 4 and 34h being stored in location 5. The Motorola 68k processors used in Apple Macintosh computers are big endian, as are IBM mainframes and Sun SPARC processors.
Unlike alignment, which can be an issue even if you are writing a program to run on only one machine, byte ordering questions don‘t commonly arise unless you are writing programs that share data between different types of computers. For example, consider a program that saves a large array of integers to disk. If this program were run on an PC compatible computer, then the integer 1234h would be stored on disk as the byte 34h followed by the byte 12h, since the computer is little endian. If someone with a Macintosh tried to read in this data file, they would read the bytes in the order saved by the PC compatible, but the Macintosh program would now interpret 34h as the MSB, since the Macintosh is big endian. So the integer value that should have been loaded as 1234h=4660d is now seen as 3412h=13330d, which is quite a difference!
So how are problems with byte ordering fixed? There are basically three common ways of dealing with byte ordering problems: Define a "universal byte ordering" for all transmission and storage. The idea here is that it doesn‘t matter what order the data is stored in the memory while a program is running -- it only matters when the data is transferred to another computer by using either a file or some sort of transmission method. For such transfers we can define a standard byte order, say big endian, and computers that don‘t use this order will have to convert data into their own byte ordering before using it. Certain data that is transmitted on the Internet uses this strategy, and uses a standard ordering that is called "network byte ordering". Require data files to indicate which byte ordering is used in that file, and require all software to be able to handle both byte orderings. The disadvantage of this method is that software must be more complex in order to deal with both possible byte orderings. The big advantage is that if a certain data file is used most often on one particular kind of computer then it can use the natural byte ordering of that computer. The TIFF image format is an example of this solution to the byte ordering problem. Special hardware that can handle both byte orderings. Many of the newer processors (such as the Power PC and the DEC Alpha) can be set into either little endian or big endian mode, so they can deal with data no matter how it is stored! This method has clear advantages, and it seems to make the byte ordering problem disappear -- however, it almost makes the problem worse by creating no clear distinction about which ordering should be "standard," and so software still has to deal with finding out which byte ordering is used by particular data.
To summarize, the byte ordering problem is another issue that arises from multi-byte data, and is most important when dealing with data that must be shared between various types of machines. What makes this problem acute in today‘s computing environment is that the two most popular machines, which should be able to share data, use different byte orderings: PC compatibles are all little endian, and Macintosh computers are all big endian.Steve Tate / University of North Texas / 940-565-4864 /srt@cs.unt.edu
Last modified: Fri May 3 12:22:59 2002