11

I'm writing a hobbyist cryptography project, and I want to ensure the data structures I define don't have padding bytes. The only assumption I've made about the environment, is that bytes are exactly 8 bits.

The structure consists of exact-width integers and pointer-sized integers, and I assume the pointer-sized integers have the same width as the machine word (for the moment, let's ignore x86-16 FAR pointers as they're 32-bit).

I've taken care to ensure that, under ILP32 and LP64 type models, the structure a) have no padding bytes and b) have sizes that're multiple of machine words. Towards making it portable on 16-bit machines, I needed to assume that no type have alignment requirement greater than the machine word size, e.g. the alignment of uint32_t is no stricter than that of uint16_t or void *.

The problem is, I don't know if I can make such assumption. So I'm asking: Are there pre-32-bit era ISAs with alignment requirements stricter than machine words? To limit scope creep, let's limit to ones that're supported as targets by a C compiler.

Update (TL;DR)

  1. I only care about octet-oriented architectures, that're supported by a C compiler.

  2. I've made my code portable on ILP32 and LP64 data models, I want to make it portable on SIP16 systems, so I need to know if I can make assumption as stated in the title. Also, I only care about native integral types (integers and pointers).

  3. Hardware reality doesn't matter as much as what ABIs say, as hardware changes are more frequent than ABI definitions.

18
  • 2
    Can confirm that the 68000 is happy with 32-bit words aligned on 16-bit boundaries — no exception generated, no speed penalty.
    – Tommy
    Feb 9 at 13:09
  • 5
    But not 68020 and later -- while they can read unaligned words, the performance will suffer.
    – lvd
    Feb 9 at 13:39
  • 2
    For TS: you can use __attribute__((packed)) (for gcc) or equivalent compiler-specific definitions to avoid structures with alignment padding. And generally you can't assume that pointer-sized integers will be the largest ones: on x64-32 ABI all addresses and pointers are 32bit, while 'machine word' is 64 bit.
    – lvd
    Feb 9 at 13:43
  • 1
    @Tommy: The 68000 has a 16-bit data bus and a 32-bit incrementer/decrementer, so any 32-bit or multi-register operation will be performed using a sequence of 16-bit addresses. A lot of graphics code for systems the Macintosh (and presumably others) were designed around this.
    – supercat
    Feb 9 at 17:12
  • 3
    There's a distinction between what the ISA requires and what the C compiler gives you by default (e.g., machine can do unaligned reads, compiler knows performance better so aligns struct members automatically). Usually there's a compiler-specific way to avoid this, but not necessarily. Feb 9 at 17:12

3 Answers 3

9

Are there pre-32-bit era ISAs with

That's a bit fuzzy, as 32 bit ISAs are older than most 8 or 16 bit ISAs, not to mention many that are smaller or larger than 32 bit.

The text makes it sound you're focusing on rather recent microprocessor architectures (mainly x86, maybe as well ARM, MIPS, etc.). Thus it would be more helpful if you could confine the kind of machines/time frame you'll want to port that software to.

alignment requirements stricter than machine words?

That's a clear No. There are no stricter requirements than the ISA word.

A machine word is by definition the basic access unit which an ISA is constructed around. Thus, in (somewhat) modern 32-bit architectures it's perfectly safe to assume 32-bit alignment.

But there are a few caveats:

  • A machine word may be more or less than 32 bits
  • It might not be an exact multiple or divisor of 32
  • There are 18, 24, 36 and 72 bit architectures (and anything you might imagine in between)

The only assumption I've made about the environment, is that bytes are exactly 8 bits.

That's valid nowadays with byte-addressable ISAs being canon. But historically

  • A byte may or may not have 8 bit.
  • Byte sizes from 6 to 9 have been commonly used.
  • The smallest accessible unit may be larger than a byte.

I assume the pointer-sized integers have the same width as the machine word

Again, that's valid with most of today's machines, but historically the same goes as with bytes:

  • A memory pointer may be smaller than a machine word
  • A memory pointer may be wider than a machine word.

To limit scope creep, let's limit to ones that're supported as targets by a C compiler.

Not really helping, as C is available for almost every machine out there, even really odd ones.


Now, with the TL;DR; added, the question almost answers itself:

No, there are not.

By assumption of SIP16/ILP32/LP64/etc. it already determines that the software will only care for exactly this setup - or, as alternative interpretation, not care at all what it's really compiled to.

This hits the age-old duality of fine/absolute control vs. perfect portability and as we all know: It's impossible to get both.


Last but not least, there may be another word size you may want to care about, the memory word and in extension thereof a cache line. Knowledge of both may bring huge benefit to performance when used accordingly.

A CPU may have a smaller or wider memory word than its machine word.

If the machine word is wider than its memory word, any misalignment that is still aligned to memory word will not result in a penalty. For example an 80386 has a 32-bit machine word but a 16-bit memory word. Performance-wise there is no difference if a 32-bit word is 16-bit or 32-bit aligned.

It gets a bit more complicated when a memory word is wider than a machine word (and used data types). For example a Pentium has a 64-bit memory word (*1). Thus any 32-bit alignment (for 32-bit values) is equally fine when looking at a single data item, as it can be fetched by a single memory access.

But as soon as this is about either a series of words or a structure longer than a single ISA word, aligning this structure to the memory word will result in notably higher performance. This is due to the first memory access fetching two words at once, thus having the second ready without need for another (slower) memory access.

This gets even more notable when caches are involved, as they are usually not organized as words but multiples thereof, called cache lines. For example, the aforementioned Pentium has a 256-bit (32-byte) cache line. That is, every memory access will (if possible) fetch 32 bytes at once, whenever a byte within is needed. As a result, it's favorable to have structures aligned to 32-byte borders, making the CPU loading the first 8 words in a single fetch, resulting in consecutive operations on multiple words within notably faster.

More modern CPUs extend this to 512-bit (64-byte) lines. Though it's not rally a new development. In the 1970s mainframes used (core!) memory words of 2, 4 or 8 ISA words to improve access speed - not to mention semiconductor cache which became standard at the time.

Bottom line, while alignment below ISA word size may be well known as cause of notable penalty, this is also true for alignment below memory word and cache line sizes.


*1 - Well, it can run on any memory size from 8 to 64 bit, but I guess it's safe to assume the 64 is the overwhelming default.

14
  • 1
    "Valid nowadays with byte addressable ISA being canon". DSPs and similar special purpose CPUs often have more than 8 bit in a byte even today. Probably not something to worry about if you're writing general purpose code, but might be.
    – Voo
    Feb 9 at 21:20
  • 2
    "A machine word is by definition the basic access unit which an ISA is constructed around." If you define "machine word" as "number of bits read at once from memory" (which is what matters for alignment), then they are quite a few architectures that pack multiple "ISA words" into a "machine word" (for example, a Cray-1 has a 64-bit MSW, but a 16-bit ISA). Often that's because a machine word represents a float, and an "ISA word" is less bits.
    – dirkt
    Feb 10 at 6:42
  • 1
    I've seen a modern MCU (i.MX RT 1060), which, while being a 32-bit Cortex-M, has memories that had all three of 16, 32 and 64 bus widths. Most, but not all, cached.
    – jaskij
    Feb 10 at 14:28
  • 2
    I'd like to challenge 'machine word' definition too. What is machine word in a contemporary x86 machine? Data width to the external memory? Cache line size? Register (which one? xmm? ymm? zmm?) size? Address size?
    – lvd
    Feb 10 at 14:48
  • 1
    The simplest way to avoid crossing cache-line boundaries is to give most types natural alignment; that is still slower, especially for page splits. But really the unit of access that matters is the cache line, not anything you could sensibly call a machine word. (That's the point I'm debating, not that alignment matters and is useful.) Feb 10 at 17:16
7

There are many machines which forbade data structures from crossing certain power-of-two boundaries that were larger than a word. If one wants to use a single 16K DMA buffer to feed audio to a DOS-era SoundBlaster(R) or compatible board, for example, the buffer would be forbidden from straddling a 64K boundary. While one could use an address whose starting offset within the 64K block boundary was anywhere between 0 and 49152, forcing an address to be a multiple of 16384 bytes would naturally take care of that requirement.

Additionally, it was and remains common for systems to set the location of a data structure by setting the high order address bits, while the low-order address bits of the data structure are fixed. The Z80 interrupt vector table, for example, must always start on a multiple-of-256 boundary, and 8086 memory segment start addresses are required to be multiples of 16 bytes.

Finally, while this is more of a software issue than a hardware one, on many 8-bit architectures it will be much easier to make a program relocatable on arbitrary multiple-of-256 boundaries than to allow arbitrary relocation anywhere, especially if the program does any tricky program-address calculations or--for the 6502--has any time-critical loops.

3
  • 2
    Technically, it's not forbidden, it is possible but might make little sense. The DMA hardware just made to operate within 64k pages as the DMA controller works with 16-bit addresses and there is a separate latch which provides the necessary upper bits for each DMA channel which the DMA controller is unaware of. So you can make a 32k transfer from a 48k offset within a 64k page, it will just transfer 16k from top of the 64k page and wrap around and transfer 16k from the bottom of the 64k page.
    – Justme
    Feb 9 at 20:52
  • 4
    @Justme: If one were to allocate an entire 64K block of memory, one could write code that exploits the fact that DMA accesses wrap at 64K boundaries, but the buffer would still not cross the boundary between two pages. When I say DMA transfers that cross block boundaries are forbidden, what I mean is that there is no way to request such a transfer that would actually result in such a transfer being performed.
    – supercat
    Feb 9 at 20:58
  • 2
    OK, but is the OP going to be encrypting such things. I was going to point out that VAX, a 32-bit machine, has some structures which demand 8-byte alignment (self-relative queue headers for one). But these are not types in C, and in any case I think encryption of them unlikely. Feb 10 at 0:43
2

From experience with working with several C compilers on 8-bit and 16-bit machines in the 1980s:

  • On 8080, Z80, and the like, nobody ever put padding into data structures. There was no performance gain there, and you could not afford to waste memory. so everything was byte-aligned.

  • Early C compilers for MS-DOS used byte alignment, because the original PC and many of the compatibles only had byte-wide memory.

  • The hardware gradually changed, but different compilers changed at different times. By the time 32-bit DOS extenders became widely used in the late eighties, natural alignment of 32-bit ints and pointers was normal, for the performance gains and the larger amounts of available memory. That posed major problems for a product I worked on, whose save file format assumed there was no padding.

  • In the mid-1990s, several customers of the product I now work on tried using the Visual C++ compiler option /Zp, which controls structure packing, apparently in the hope of saving memory. Since the API they were calling passes structs by value, they got plenty of crashes, and we warned against this in the documentation.

2
  • My recollection is that compilers for the 8088/8086 almost always had a compiler option to either force 16-bit alignment or not. Were there any that didn't?
    – supercat
    Feb 11 at 18:42
  • @supercat: Sorry, don't know. Feb 11 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.