Endian refers to a processor addressing model that defines the byte ordering of data and instructions stored in computer memory. The most common addressing models are Big-endian (left-to-right order) and Little-endian (right-to-left). Intel-based processors (80x86, Pentium, and the like) are Little-endian, while others (such as the Motorola 680x0 in the Macintosh) are Big-endian. Still others, particularly the PowerPC, are "Bi-endian," allowing them to run in either Big-endian or Little-endian mode (see the accompanying text box entitled "PowerPC Bi-Endian Capabilities," by James R. Gillig).

As straightforward as this sounds, "endianness" can be confusing for programmers--particularly when developing portable software running on a variety of platforms. To address this confusion, I've developed an "endian engine" which handles every byte order. This engine is presented in my article "Your Own Endian Engine," (Dr. Dobb's Journal, November 1995). The heart of the engine is a powerful set of C macros that perform bitwise operations, which I'll discuss in this article. It's noteworthy that the examples I implement to handle these C macros are designed to handle instructions for MMIX, a hypothetical computer developed by Donald Knuth (see the accompanying text box entitled "MMIX: Knuth's New Computer").

Many of the macros here use bit numbering. By convention, the least significant bit (LSB) is bit 0. Some of the macros indicate one or more contiguous bits in a value, using the convention of a start-bit number and a length in bits. You give the bit number of the lowest bit in the range of bits that you want. For instance, to use bits 0 through 3, give a start-bit number of 0 and a length of 4.

Conveniently, a variety of specifications and standards adhere to the LSB convention of numbering as bit 0. Most Intel processors, the IEEE MUFOM (microprocessor universal format for object modules), and the MIL-STD FORTRAN functions all use this convention. The only major exception is IBM mainframes, which number the most significant bit (MSB) as bit 0.

Since at least the 1970s, many versions of Fortran have included a standard set of bit functions that include the usual operations: AND, OR, NOT, and exclusive-OR. These Fortran functions also include routines for bit extraction, insertion, shift, and circular shift. Rather than reinvent the wheel, I've used the same function names and operand orders. However, since the Fortran functions were designed for implementations with just one integer type, and C has many sizes of integer types (ranging from char to long), I added, where necessary, an additional parameter (at the end) to indicate the data type to be returned. This must be some unsigned integral type.

As for the Fortran-inspired macros, I'll start with NOT(value,type) (bitwise complement), sometimes called the "flip bits" or "invert" operation. In Fortran, the NOT(value) function has one operand (an integer value) and returns an integer: the inverted value. The C NOT(value,type) macro has an additional operand, which must be an unsigned integral data type. The NOT(value,type) macro converts the given value to the given type and returns the converted value with all of the bits inverted. For instance, in an implementation with 8-bit characters, NOT(0xF0, unsigned char) would be 0x0F.

The IAND(m,n,type) ("integer and") macro simply performs a bitwise-AND of the bits in the first two operands, which are treated as type type, and returns the result. It supports any unsigned integer type for its operands. Kenneth Hamilton used the Fortran version of this macro in his article "Direct Memory Access from PC Fortrans" (Dr. Dobb's Journal, May 1993). Hamilton's code needed to extract the low byte from some integer value. Using the C macros in bitops.h, the equivalent would be:

unsigned int ic1;
ic1=IAND(ic,255,unsigned int);

There is an integer extract bits (IBITS) macro that extracts and right-justifies one or more contiguous bits from a given value. IBITS is called as IBITS(value,bitnum,len,type). For instance, IBITS(0x5678,8,4,unsigned long) returns an unsigned-long value of 0x6.

Another Fortran-inspired macro is the integer shift (ISHFT) macro, a call to which appears as ISHFT(value,shifts,type). ISHFT and its circular-shift companion ISHFTC are unique in that they indicate the direction to shift by positive or negative values of the shifts parameter. A positive value for shifts causes a left shift by that many bits; a negative value causes a right shift by that many bits; a 0 value causes no shift. Make sure the absolute value of shifts is less than or equal to the size of type in bits; otherwise, the result is undefined.

For a Fortran version of the ishft routine, see Ray Duncan's "16-Bit Software Toolbox" column (Dr. Dobb's Journal, August 1985).

In the examples from here on, I'll use the bitops.h C macros to handle instructions for MMIX. The parts of an MMIX instruction are multiples of 8 bits each, but the bitops.h macros don't depend on this.

C provides some powerful bitwise operators, although you need to be careful regarding the widening of values between different data types. The macros in bitops.h provide a more complete set of bitwise operations than bare C, with protection against widening problems, although you must avoid macro arguments with side effects. You should also avoid using any of the signed data types with the macros.

ANSI X3.159-1989, American National Standard for Information Systems--Programming Language--C. New York, NY: American National Standards Institute (ANSI), 1989.

Knuth, Donald E. MMIX. Private communication, August 20, 1992.

MIL-STD-1753. Military Standard: FORTRAN, DOD Supplement to American National Standard X3.9-1978. November 9, 1978. Available free from the Defense Printing Service at 215-697-2179.

MMIX: Knuth's New Computer

Back in the 1960s, Donald Knuth designed a hypothetical computer called "MIX" for his Art of Computer Programming algorithms books. MIX shows its age in various ways, so Knuth is designing a RISC-like successor called "MMIX" (short for "Meta-MIX" or "Mega-MIX"). He started from scratch to avoid the restrictions of the old architecture. The new computer incorporates Big-endian byte ordering, byte addressing, two's-complement integer arithmetic, and IEEE floating-point arithmetic.

Knuth has not yet published his description of MMIX. His latest draft is dated August 20, 1992. He expects to make many technical changes in his next draft, due sometime in 1995, so details given here may change as well.

Knuth plans to use MMIX for the later volumes of the Art of Computer Programming series. I myself hope to write a cross assembler and simulator for MMIX for publication in Dr. Dobb's Journal. This drives my exploration of "big-integer" (64-bits or more) routines for C, as well as 64-bit, portable object-file formats (like MUFOM and ELF).

In MMIX, Knuth has adopted the common definition of a byte as having 8 bits. He is much more generous with registers; MMIX has 256 general-purpose registers. Knuth has also accounted for other practical issues this time. His description of MMIX floating point acknowledges that on some models, the system may trap floating-point "instructions" and interpret them in software. MMIX is supposed to have virtual memory, although the current draft doesn't seem to have enough detail for an operating system to deal with page faults or page tables.

The 1992 draft defines a 32-bit system, but Knuth is likely to convert to 64 bits before he publishes the final version. He has also had second thoughts about a number of complications the draft introduced: regions, probable branches, and delay slots, for example.

Regions are a simple way to provide multiple address spaces, kind of like segment registers. The delay slot avoids having to refill the prefetch buffer because of the branch. I first saw delay slots being used on the MIPS when I worked at Microsoft. Many of us with previous assembly-language experience kept forgetting that the instruction in the delay slot would execute, too.

Probable branches and delay slots are, in my opinion, architectural warts to improve pipeline performance while driving the assembly-language programmer crazy. In a pipelined system, the instruction right after a branch has already been prefetched, so why not execute it?

It seems, however, that Knuth is reconsidering these additions, and they will probably be dropped from the next draft.

--J.R.

PowerPC Bi-Endian Capabilities

Jim Gillig

James R. is a software engineer on OS/2 and IBM Workplace technologies in Boca Raton, FL. He can be reached through the DDJ offices.<

The PowerPC is a Bi-endian RISC processor that supports both Big- and Little-endian addressing models. The Bi-endian architecture provides hardware and software developers with the flexibility to choose either mode when migrating operating systems and applications from their current BE or LE platforms to the PowerPC. Program instructions are like multibyte-scalar data and are subject to the byte-order effect of Endianness.

Each individual PowerPC machine instruction occupies an aligned word in storage as a 32-bit integer containing that instruction's value. In general, the appearance of instructions in memory is of no concern to the programmer. Program code in memory is inherently either a LE or BE sequence of instructions even if it is an Endian-neutral implementation of an algorithm.

How does the PowerPC handle both LE and BE addressing models? The processor calculates the effective address of data and instructions in the same manner whether in BE mode or LE mode; when in LE mode only, the PowerPC implementation further modifies the effective address to provide the appearance of LE memory to the program for loads and stores.

The operating system is responsible for establishing the Endian mode in which processes execute. Once a mode is selected, all subsequent memory loads and stores will be affected by the memory-addressing model defined for that mode. Byte-alignment and performance issues need to be understood before using an endian mode for a given application. Alignment interrupts may occur in LE mode for the following load and store instructions:

• Fixed-point load instructions.
• Fixed-point store instructions.
• Load-and-store with byte-reversal instructions.
• Fixed-point load-and-store multiple instructions.
• Fixed-point move-assist instructions.
• Storage-synchronization instructions.
• Floating-point load Instructions.
• Floating-point store instructions.

A very powerful feature of the PowerPC architecture is the set of integer load-and-store instructions with byte reversal that allow applications to interchange or convert data from one Endian type to the other, without performance penalty. These load-and-store instructions are lhbrx/sthbrx, load/store halfword byte-reverse indexed and lwbrx/stwbrx, load/store word byte-reverse indexed. They are ideal for emulation programs that handle LE-type instructions and data, such as the emulation of the Intel instruction set and data. These instructions significantly improve performance in loading and storing LE data while executing PowerPC instructions in BE mode and emulating the Intel instruction behavior; this eliminates the byte-alignment and data-conversion overhead found in architectures that lack byte-reversal instructions. Currently, these instructions can be accessed only through assembly language. Until C compilers provide support to automatically generate the right load and store instructions for this type of data, C programs can rely on masking and concatenating operations or embed the assembly-language byte-reversal instructions.

MMIX_Instr_T  New_Instr = ALL_ZERO_BITS(MMIX_Instr_T);
/* Set opcode. */
MVBITS(
      0xC2,                    /* ADDU opcode */   /* src */
      0,                       /* src index: src bit 0. */
      MMIX_INSTR_OPCODE_LEN,   /* len */
      &New_Instr,              /* dest ptr */
      MMIX_INSTR_OPCODE_START, /* dest index */
      MMIX_Instr_T);           /* type */
/* Set X (target) field to say r40. */
MVBITS(
      40,                     /* register 40 */  /* src */
      0,                      /* src index: src bit 0. */
      MMIX_INSTR_X_LEN,       /* len */
      &New_Instr,             /* dest ptr */
      MMIX_INSTR_X_START,     /* dest index */
      MMIX_Instr_T);          /* type */
/* Set Y (a source field) to r41. */
MVBITS(
      41,                    /* register 41 */  /* src */
      0,                     /* src index: src bit 0. */
      MMIX_INSTR_Y_LEN,      /* len */
      &New_Instr,            /* dest ptr */
      MMIX_INSTR_Y_START,    /* dest index */
      MMIX_Instr_T);         /* type */
/* Set Z (the other source field) to r42. */
MVBITS(
      42,                   /* register 42 */  /* src */
      0,                    /* src index: src bit 0. */
      MMIX_INSTR_Z_LEN,     /* len */
      &New_Instr,           /* dest ptr */
      MMIX_INSTR_Z_START,   /* dest index */
      MMIX_Instr_T);        /* type */
      

#include "mmixcom.h"  /* MMIX_Word_T, MMIX_WORD_LEN, etc. */
MMIX_Word_T
Sim_SRU(  /* Simulate shift right unsigned instr. */
   MMIX_Word_T  Source_Reg,
   MMIX_Word_T  Shift_Count_Reg)
{
   if (Shift_Count_Reg >= MMIX_WORD_LEN)
      return (0);
   return (RIGHT_SHIFT_BITS(
         Source_Reg,            /* value */
         Shift_Count_Reg,       /* shifts */
         MMIX_WORD_LEN,         /* len */
         MMIX_Word_T));         /* type */
}

Copyright © 1995, Dr. Dobb's Journal