How was the C language ported to architectures with non-power-of-2 word sizes?

Question

By the time the C language started to gain popularity outside of the PDP-11 circles (mid-1970s), mainframes with "weird" word sizes, and no capability to address individual bytes efficiently were still in use: for example, Wikipedia mentions

• CDC 6600 (1964) with 60-bit words using 6-bit chars,
• PDP-6/PDP-10 (1963/1966) with 36-bit words using 6-bit or 9-bit chars,
• Electrologica X8 (1965) - the chronologically last one in the table with a non-power-of-2 word size - with 27-bit words using 6-bit or 7-bit chars.

CDC 7600 (1969) is not listed but it had the same architecture as CDC 6600.

Were there successful C language implementations (commercially or widespread informally) for those architectures, and how was it done?

Incidentally, on the BESM-6 (1967) with 48-bit words using 8-bit bytes, the C language was but a toy, implemented as Johnson's PCC porting experiment, and hasn't reached a quality of implementation good enough for practical use.

Answer 1

There is some code left over in the pcc codebase showing how the GCOS compiler (for the Honeywell/GE 6000 series) worked, it used 9-bit (ASCII, most likely) characters natively, but supported 6-bit BCD characters with `STRING` syntax for encoding them in the source.

The lexer support for these string tokens can be seen at old/pcc/mip/scan.c, the strtob function it calls is not present in the code, but may have been a library function available on those systems. According to this B language reference manual (B was an earlier language by Ken Thompson and Dennis Ritchie), B had similar syntactic support and dual BCD/ASCII strings, and the print function (like C's sprintf) could be used for converting from BCD to ASCII.

On further refinement of my google searches, I was able to find a C manual for GCOS. BCD strings could be printed with %_s (and had been %b in early versions), and various library routines for working with the BCD characters (which are packed six per 36-bit word) are documented.

Answer 2

Word size is not really an issue in implementing C on a given architecture. There's no requirement that C types have a power-of-two size. There's only a problem if the word size is too small, but this can be simply worked around by using multiple consecutive words to represent C types like int and long. There's a long list of C compiler implementations for 8-bit and 16-bit targets that do this.

The problem with porting C is with the size of a byte, which C defines as the smallest addressable unit and the size of the char type. The size of a byte doesn't need to be a power of two (for example, there was a fairly early port of C to the 9-bit byte, 36-bit word Honeywell GCOS mainframes), but it does need to be a least 8 bits. If it's smaller than that, then it's awkward to work around, and as far I know C has rarely if ever been ported to machine with a natural byte size smaller than 8 bits.

If the size of a smallest addressable unit is significantly larger than 8-bits, then this also causes problems. While there's no conformance issue with this, having a such a large byte size would mean that ordinary ASCII (or EBCDIC) character strings end up wasting a lot of memory. C compilers that were implemented on systems where the smallest addressable unit was 16 bits or larger made char an 8-bit (or maybe 9-bit) type and thus made a C byte the same size.

In order for the C compiler to make the size of a C byte be smaller than the target machine's smallest addressable unit, the compiler needs to generate special code to extract the smaller C bytes out of the larger native bytes. This also means that the C compiler needs to handle pointer to char (char *) types differently. Typically, they were larger than other pointer types in order to store extra bits denoting which part of a native byte was being pointed to. This, in turn, meant that the pointer to void types (void *) also needed to be larger than most other pointer types.

All of this is supported by the C standard. A byte is required to be at least 8 bits in size. The size of char is required to be one byte. The size of short, int, long, and long long are required to be at least 16 bits, 16 bits, 32 bits, and 64 bits, respectively. All of these types are required to be integer multiples of the byte size. There's no requirement that any of these types be a power of two in size. Pointer sizes and representations are allowed to vary according to the type being pointed to.

If you want to write strictly conforming C code that works on any compliant C compiler ever made, then you can't depend on the size of types being nice, even powers of two. You should also be prepared to deal with padding bits, trap representations, integer overflow exceptions, and non-twos-complement arithmetic.

Answer 3

The TI TMS34010 Graphics System Processor was capable of addressing memory in any particular transfer size you liked (2, 4, 6, 8, whatever bits). This was a natural outgrowth of its focus on graphics, where different color depths might be represented by different #s of bits per pixel.

The C implementation simply deviated from the standard, and had the pointers be 32 bit, BITWISE pointers. The bus was 32 bits, and if your access straddled a 32 bit boundary, the CPU would simply do the extra memory accesses to make it transparent to the code.

This did mean that you had to pay attention to what you were doing when you were doing pointer math, but other than that it was quite pleasant to use.

Answer 4

An interesting contemporary example is the Analog Devices SHARC 21488 and friends.

sizeof(char) == sizeof(short) == sizeof(int) == 1

This is fully compliant with the C standard (But not POSIX), and given that the usual use for these parts is as special purpose audio processors the extra space for character strings is not a problem.

Answer 5

AT&T's 1984 official The C Programming Handbook recognizes one compiler with 9-bit chars.

Plus another compiler in EBCDIC!

Simply put, there is nothing inherent in C that would require word size to be a power of 2. The reason we expect it today is because all modern systems do so, in turn related to computing history.

In one word: packaging.

Summary

1. There is no absolute reason why word size has to be a power of 2.
2. For mainframe/minicomputers, the size of an IC package is irrelevant. The computers are built from individual low-level logic chips, so they could (and often did) have strange word sizes.
3. The first microprocessor was 4 bits because of packaging constraints.
4. For several reasons, microprocessor word size has grown by doubling. Thus, microprocessor word sizes have become powers of 2.
5. Microprocessor speed was severely limited by packaging limitations, until they started using larger non-DIP packages. Then microprocessor speed surpassed mainframe/minicomputers, leading to the demise of the latter.
6. Because nearly every computer today is built from microprocessors, we mistakenly assume that word size always must be a power of 2.

(1) No C requirement for a power of 2.

This manual was written in 1984 by AT&T Bell Labs to train programmers to write in C. It was published in the time between the 1st and 2nd editions of Kernighan and Ritchie. .

Compilers have been written for at least one platform with a non-power-of-2 word size. Examine the entry for the Honeywell 6000: .

Also note that C doesn't have to be in ASCII; the entry for the IBM 360/370 shows EBCDIC.

The 2nd edition of K&R reinforces this point:

Each compiler is free to choose appropriate sizes for its own hardware, subject only to the restriction that shorts and ints are at least 16 bits, longs are at least 32 bits, and short is no longer than int, which is no longer than long.

Kernighan and Ritchie, The C Programming Language, 2nd edition, 1988. p. 36

Do characters have to be individually addressable by hardware? No, there have been plenty of systems that load/store whole words and then let the compiler do the magic. On the Honeywell 6000, sometimes programmers would pack 5x 7-bit mixed-case ASCII, or 6x 6-bit upper-case ASCII, into one 36-bit word. This was especially popular in COBOL programs to save memory.

Do larger data sizes have to be a whole multiple of smaller data sizes? In theory, no. You could theoretically have 9 bit char, 15 bit short, and 33 bit longs. In practice, either the processor or the compiler has to deal with this weirdness, and it's not a trivial task. So in practice, every compiler ever made has simply made all data sizes a multiple of a char.

(2) Mainframes and minicomputers

Early computers were constructed from individual vacuum tubes, transistors, or small-scale integrated circuits (such as the 7400 and 74000 series). Those that filled an entire room were generally called mainframes, whereas minicomputers were typically the size of one equipment rack or smaller. The former usually had more memory, mass storage, and peripherals than the latter, hence the increased size and cost.

Designers of these systems picked a word size that was appropriate for their needs. Many systems had word sizes that weren't powers of 2. The GE 600 (and its successor the Honeywell 6000) had 36 bits. The PDP 8 had 12 bits. The Nicolet 1080 had 20 bits.

Because the processor is not confined to one chip, it didn't matter how many pins were on the ICs that were used. If one IC wasn't enough for your needs, you just wire up more. That's why these computers took up so much space and cost.

On the other hand, these computers could be quite fast. With full-sized address and data buses, they could load or store an entire word in just one clock cycle.

(3) The first microprocessor

Microprocessors consolidate all arithmetic, logic, and control functions on to one integrated circuit. The Intel 4004 is often cited as the first microprocessor.

Side notes: Some claim the MP944 as the first microprocessor, but it was a military design that was classified until 1998, so it had no impact on future processor design. Microcontrollers are one-chip solutions that also include ROM, RAM, and I/O on one chip; most of what I say about microprocessors also applies to microcontrollers.

The 4004 project was initiated by a customer who wanted to build a calculator. Intel quickly realized that the customer's design would require a 40-pin package, when Intel had manufacturing equipment only for 16-pin chips. Thus, the design was scaled back to using 4-bit words. Conveniently, 4 bits is just enough to support the binary-coded-decimal used in a calculator.

Although the 4004 is 4 bits wide externally, it uses 8-bit instructions and 12-bit addresses. This is accomplished by multiplexing the external bus for both address and data. Loading or storing data requires three cycles for the address and one cycle for the data; an instruction fetch uses three cycles for address and two for the instruction.

This "bus bottleneck" was a result of packaging limitations, made the 4004 much slower than a similarly-clocked minicomputer would be. It also required extra hardware outside the chip to decode and latch signals. These issues would continue for about another 25 years in further microprocessor architectures.

(4) Word sizes double

Four bits is simply not enough for most applications (especially not a calculator). However, one can create larger data types by operating on multiple words. For example, you can add two 8-bit numbers by combining the additions of two pairs of 4-bit numbers.

You could hypothetically use a similar process to add 12-bit numbers. (This was in fact used in the 12-bit Intersil 6100 used by the PDP-8.) However, as long as you have written the code to add two 8-bit numbers, why not re-use that code to add two 16-bit numbers? And then re-use that to add 32-bit numbers? You can see how this doubles the number of bits each time you increase the data size, leading to data sizes that are powers of 2.

Another issue with the 4004 was that the instruction size was two words (8 bits). Even later processor designs often required some multi-word instructions. If you double the bits of the external bus, it will take fewer cycles to fetch instructions.

Powers of 2 are also attractive to computer designers, as they are already familiar with them through other aspects of computing.

Thus, Intel's next processor (the 8008) had double the word size of the 4004: 8 bits. The package now had 18 pins, again creating a bus bottleneck. This was followed by the 8080, which had 40 pins, was much faster, and was easier to interface.

Other processors entered the market after the 8008. By then, the usefulness of word sizes that are powers of 2 had already been established, and processor designers eagerly accepted them.

(5) New packaging overcomes limits

Business users continued to purchase mainframes and minicomputers into the mid-1990s, as they were significantly faster than microprocessor-based machines. The reason was the bus bottleneck imposed by microprocessor packaging.

Until the 1990s, most processors were housed in dual inline packages (DIP). Most designs had 40 pins or less, although the Motorola MC68000 is an impressive exception at 64 pins. As the number of pins on a DIP grows, the package takes up a lot more board space, and the wires that connect the corner pins grow longer, which is a bad thing at high frequencies. Thus, microprocessor designers did their best to limit pin count, even if this meant reducing the size of external buses. This causes the bus bottleneck, previously described.

In contrast, mainframes and minicomputers use as many chips as they need to build the processor. Buses are the full width throughout the machine, so there is no bus bottleneck, making them faster than contemporary microprocessors.

During the 1990s, chipmakers began using other forms of packaging, such as quad flat packs, plastic leadless chip carriers, pin-grid arrays, and ball-grid arrays. These new forms allowed more than 40 pins, enabling larger external microprocessor buses.

Freed of the bus bottleneck, microprocessor instruction speeds increased dramatically. Of course, there were other factors in play. Tricks such as caching and pipelining were "borrowed" from mainframes. Reduced Instruction Set Computing (RISC) made one-cycle instruction fetches. Smaller transistor sizes and computer-aided chip design helped increase the number of transistors per chip, as well as boost clock speeds. Compilers became smarter. Regardless, microprocessors quickly outpaced the speed of mainframes and minicomputers.

(6) Computers today

Mainframes and minicomputers became obsolete by the end of the 1990s. Why bother making a system out of discrete chips when a microprocessor is cheaper, smaller, and faster? Of course, there are still room-sized computers -- but they are now server farms made of hundreds or thousands of microprocessors, not discrete chips.

Practically all computers today use microprocessors, which in turn have word sizes that are powers of 2. Thus, we often assume that a processor's word size has to be a power of 2. Although practical, it is not a requirement.