3 ms·

What does "self-synchronizing" mean in this context? I've never heard of a self-synchronizing instruction stream. Does it just mean "memory-aligned"?

kmeisthax 8y ago
No. Memory-aligned means that instructions can only exist on certain addresses. (It also implies a minimum instruction length.) On most RISC architectures, instructions are also a constant size, with the same alignment. For example, a MIPS instruction stream consists of 4-byte instructions aligned to every fourth byte in memory. Memory alignment and constant instruction size ensure that any given instruction stream can only be executed as itself, or part of itself. Note that this is not self-synchronization - if you removed a byte from an instruction stream, you would get a wildly different instruction stream. (I said MIPS because ARM instruction streams can be THUMB, which permits a different instruction interpretation for the same stream, and thus defeats the security advantages of memory alignment requirements.) Self-synchronizing means that each subdivided unit (usually byte) of a stream also indicates if it is the start of a new symbol within that stream. For example, UTF-8 is an example of a self-synchronizing byte stream. In UTF-8, encoded codepoints have variable-length representations. However, the upper bits of each byte clearly indicate not only if the byte is the start of a new codepoint, but how many bytes follow to complete the codepoint. This means that a deleted or altered byte will only delete or alter the symbol it's a part of, and not any other part of the stream. Self-synchronization and alignment requirements address the same problem - ambiguous instruction streams - by different methods. Memory alignment prohibits you from reinterpreting the stream; while self-synchronization makes doing so less valuable.
- Dylan16807 8y ago
  But do any self-synchronizing instruction sets exist? (And are in commercial silicon?) It seems like it would be very annoying for density and constant-encoding reasons with 8 bit code units, and none of the variable 16/32 bit encodings I can name do it either.
  - dezgeg 8y ago
    The PIC18 instruction set has this property. Most instructions take up a single 16-bit instruction word, but the few ones that take up 2 words all have the 0b1111 in the high bits of the second word, which would execute as a NOP if branched into. This encoding is presumably a consequence of the instruction set containing conditional skip instructions. That is, the skip instructions don't have to parse the instruction stream for 2-word instructions but can always just skip a single instruction word and let the second word execute as a NOP.
- mehrdadn 8y ago
  Ohh, thanks! Now I recall I'd heard the term regarding UTF-8 at some point but completely forgotten about it. It reminds me very much of prefix-freeness. Is it fair to say that that's what we really need (without alignment)? It seems self-synchronizing is a bit stronger (no pun intended) but not necessarily necessary to ensure you can't jump into the middle of an instruction?
deleted 8y ago
[deleted]

kmeisthax 8y ago

No. Memory-aligned means that instructions can only exist on certain addresses. (It also implies a minimum instruction length.) On most RISC architectures, instructions are also a constant size, with the same alignment. For example, a MIPS instruction stream consists of 4-byte instructions aligned to every fourth byte in memory. Memory alignment and constant instruction size ensure that any given instruction stream can only be executed as itself, or part of itself. Note that this is not self-synchronization - if you removed a byte from an instruction stream, you would get a wildly different instruction stream. (I said MIPS because ARM instruction streams can be THUMB, which permits a different instruction interpretation for the same stream, and thus defeats the security advantages of memory alignment requirements.) Self-synchronizing means that each subdivided unit (usually byte) of a stream also indicates if it is the start of a new symbol within that stream. For example, UTF-8 is an example of a self-synchronizing byte stream. In UTF-8, encoded codepoints have variable-length representations. However, the upper bits of each byte clearly indicate not only if the byte is the start of a new codepoint, but how many bytes follow to complete the codepoint. This means that a deleted or altered byte will only delete or alter the symbol it's a part of, and not any other part of the stream. Self-synchronization and alignment requirements address the same problem - ambiguous instruction streams - by different methods. Memory alignment prohibits you from reinterpreting the stream; while self-synchronization makes doing so less valuable.

Dylan16807 8y ago
But do any self-synchronizing instruction sets exist? (And are in commercial silicon?) It seems like it would be very annoying for density and constant-encoding reasons with 8 bit code units, and none of the variable 16/32 bit encodings I can name do it either.
- dezgeg 8y ago
  The PIC18 instruction set has this property. Most instructions take up a single 16-bit instruction word, but the few ones that take up 2 words all have the 0b1111 in the high bits of the second word, which would execute as a NOP if branched into. This encoding is presumably a consequence of the instruction set containing conditional skip instructions. That is, the skip instructions don't have to parse the instruction stream for 2-word instructions but can always just skip a single instruction word and let the second word execute as a NOP.
mehrdadn 8y ago
Ohh, thanks! Now I recall I'd heard the term regarding UTF-8 at some point but completely forgotten about it. It reminds me very much of prefix-freeness. Is it fair to say that that's what we really need (without alignment)? It seems self-synchronizing is a bit stronger (no pun intended) but not necessarily necessary to ensure you can't jump into the middle of an instruction?

deleted 8y ago

[deleted]