8 ms·

What happens when you shift a register by more than the register size?

100 points by signa11 3y ago

Waterluvian 3y ago
What about if you rotate a register by more than the register size? Does it just rotate a few laps around the register unnecessarily? Does it optimize? Does it not work?
- kevin_thibedeau 3y ago
  Barrel rotators will just take the lower n-bits they need to perform a full word rotation. Extras are ignored as it's a modular operation.
Aardwolf 3y ago
> On the 8086, the shift amount is given by the 8-bit cl register. The running time of the instruction is proportional to the number of bits shifted, and the processor does not optimize shifts that are larger than the register size, so if you ask to shift by 255 places, it will run a loop 255 times. Wasn't this also the case on Pentium 4 (with different max value than 255), when they removed the barrel shifter?
- adrian_b 3y ago
  No. On all Intel and AMD CPUs starting with 80186 and 80286 (which have been launched simultaneously) only the lowest 5 (or 6 for 64-bit operations) bits of the shift value are used. All the other bits are ignored. It does not matter how the shift operation is implemented, with a barrel shifter or without it. The implementation influences only the execution time of the instruction, not its effects. This difference in the behavior of the shift and rotate operations was used by many programs to identify whether they were executed on an 8086/8088 or on an 80186/80188 (or a later) CPU. This was important, because 80186 had introduced some new useful instructions, and the standard means of detecting CPU features with the CPUID instruction has been introduced only more than a decade later, in Intel Pentium (1993). The detection of the CPU was based on the fact that shifting left a 16-bit register by 32 will not change it on an 80186 or later CPU, but it will produce the result zero on an 8086/8088.
- ack_complete 3y ago
  No, shifts were slow on the Pentium 4 but still constant timing regardless of shift distance, and they weren't microcoded.
deleted 3y ago
[deleted]
dgellow 3y ago
I said it multiple times over the years but Raymond Chen has been my favorite technical author for the past 10+ years and is always such a pleasure to read. Little anecdotes and pieces of history that make you think and dig more into various topics.
- intelVISA 3y ago
  [flagged]
  - pavlov 3y ago
    Did this comment fall out of a 1995 time warp?
  - dgellow 3y ago
    Strange thing to comment. He’s there since decades (92? I remember him mentioning a date beginning 90s on a C++ podcast episode) and seems to be I pretty good at his job. It’s clear he’s there because he wants to.
- bombcar 3y ago
  Every single one of his posts is posted from a place of pain, it's pretty obvious. So some horrible bug involving shifting registers ate a portion of his life, and we get a cool blog post.
  - dgellow 3y ago
    Now that you say this, I really appreciate his writing style doesn’t project frustration. He has his way to make me curious about some weirdly technically specific errors, bugs, misconceptions without ranting or complaining. It always feels like a friend shared a nice little thing they would have learned the hard way over the years.
- nanoxide 3y ago
  I just wish there weren't so many rather C++ focused posts. The last few months weren't really that interesting for me. I get that there's a limited amount of fun Windows stuff and anecdotes, but these deep dives into Windows API C++ intricacies don't really fit his usual topics
ot 3y ago
I used to do a lot of bit twiddling (for compression) and the fact that shift values of 64 (for 64-bit integers) always have to be special-cased, instead of just zeroing out the value, is so annoying and inefficient. I really wish it just worked in hardware.
- IshKebab 3y ago
  I totally agree. I can understand why they don't allow it but it definitely makes code more awkward.
  - thrtythreeforty 3y ago
    It would be about 64 gates. Sort of irritating that it doesn't work, to be honest.
- jleahy 3y ago
  Well it does work in hardware, but not with the normal shift instruction. Just use a ‘double shift’ which you can get with __int128 (or with inline asm, or just full asm).
nkurz 3y ago
Since it hasn't been mentioned yet, I'll point out that the article is about how hardware processors react to assembly level shifts with greater than register size. Unless you are programming directly in assembly, the most important take-home from the article is probably the "Bonus chatter" at the end: shifts equal to or greater than register size are undefined in C and C++. How the CPU would handle the theoretical assembly instruction is usually of little importance when demons are flying out of your nose. Here's Regehr on some of the standard ways to protect yourself from a malicious or overzealous compiler when you need to have a function that does variable sized rotations: https://blog.regehr.org/archives/1063 https://blog.regehr.org/archives/1063
- fao_ 3y ago
  I mean, I feel a sane reading of the C Standard means reading "undefined" as "unspecified by the standard, but dependent on the trust and common sense of the compiler authors" -- which, you know, I don't know that that's any worse than "dependent on the trust and common sense of the npm package author" or "dependent on the trust and common sense of the rust cargo maintainer". Like, yes theoretically the compiler can do anything, but tangibly, coherently, most compilers deal with most UB in a sane way.
  - loup-vaillant 3y ago
    > but tangibly, coherently, most compilers deal with most UB in a sane way. It depends. In some cases, really, no they do not. Compilers have been caught deleting security checks when they noticed that the only way to reach the error case was to trigger UB… and since "UB doesn't exist", the error case is considered dead, and the whole test is deleted. Sometimes this leads to remote code execution vulnerabilities, that if exploited could actually result in your hard drive being encrypted, or a keylogger being installed. UB is really, really scary.
    - bippihippi1 3y ago
      cite source?
orlp 3y ago
You can get well-defined behavior at 0 cost (for x86-64 and ARM64, which covers most everything not very obscure/embedded) on both GCC and LLVM by explicitly adding a modulo operator: uint32_t foo(uint32_t x, int s) { return x << (s % 32); } foo(unsigned int, int): shlx eax, edi, esi ret
- Someone 3y ago
  Is that well defined for foo(0x12345678, -1) ? I think that, in modern C -1 % 32 == -1 (% computes the remainder, not the modulo) it would try to compute x << -1 and AFAIK that’s undefined behavior. Even if it is well-defined, it possibly is not what you want. If you were to call foo(0x12345678, 32) I think the most logical result would be zero, but the code you give returns 0x12345678.
  - dzaima 3y ago
    Yeah, to be well-defined it should be 's & 31', or use an unsigned type for s; compiler explorer comparing those under ubsan shows the original having the possibility of UB: https://godbolt.org/z/eT9q871bY https://godbolt.org/z/eT9q871bY
  - orlp 3y ago
    You're right I was sloppy in defining s to be an int, it should've been an unsigned type. My point was more about getting consistent behavior across platforms at (most often) zero cost, not to support arbitrary negative shifts.
hasmanean 3y ago
If you’re shifting right, the behaviour ought to be Unsigned: should produce a zero Signed: should sign extend the leftmost bit, so it will either be 0 or -1 Shifting left should result in a 0.
kazinator 3y ago
Should be "by the register size or more" not "by more than the register size". Machine-specific behavior starts at register size, not beyond! That's why in C, the behavior is undefined.
dzaima 3y ago
Note that this is only for the direct shift instructions. Some other related instructions, and SIMD versions, might be different from the regular shifts on the same architecture. x86-64's 'bzhi' instruction (does 'a & ((1<<b) - 1)') uses mod 256 (and thus, if mod 32/64 was specified in C, compilers couldn't optimize to this). ARM NEON's SIMD shifts merge both left and right shift in one instruction (reads low 8 bits as a signed int, positive being left shift, and negative - right shift)
- lifthrasiir 3y ago
  > if mod 32/64 was specified in C, compilers couldn't optimize to this This reads a bit ambiguously, though the conclusion would be same. If C specification had that requirement, yeah, they have to do mod 32/64 every time integers with unknown bounds are used for `b`. But then Intel should have noticed this first and define LZHI to use mod 32/64 according to the operand, or make two versions of LZHI. If C code had that requirement, for example, by always using `a & ((1 << (b & 31)) - 1)` to avoid an UB, compilers indeed would not be able to optimize it into a single BZHI. But they can use AND+BZHI, and I think BZHI has only a half of throughput than AND in almost all supported processors, so an excess AND probably can't do much harm.
  - dzaima 3y ago
    True, Intel could've been influenced if there was an expectation on the behavior of shifts. But I doubt they'd have made two versions, and we'd just be stuck with the less useful mod 32/64 one.
cvccvroomvroom 3y ago
Ah, the olden days of 8086. When xor ax, ax was faster than mov ax, 0 and so was xor ax, bx; xor bx, ax; xor ax, bx to swap instead of using a temporary. Some processors also have ror and rol instructions that accomplish shifting in the shifted out bits. 8086 also had rotate with carry flag: rcr and rcl. Aids implementing sign-extended shift right and arbitrary precision math.
- Narishma 3y ago
  > Ah, the olden days of 8086. When xor ax, ax was faster than mov ax, 0 That's still the case today, no?
  - th3typh00n 3y ago
    Yes, for 32- and 64-bit registers. Most modern x86 CPUs has fast paths for 'xor reg, reg' which performs the zeroing using the register renaming mechanism instead of actually executing anything on the back-end. So the only cost is that of decoding the instruction.
rolph 3y ago
Barrel Shifter: https://en.wikipedia.org/wiki/Barrel_shifter https://en.wikipedia.org/wiki/Barrel_shifter also : https://www.geeksforgeeks.org/overflow-in-arithmetic-addition-in-binary-number-system/ https://www.geeksforgeeks.org/overflow-in-arithmetic-additio... https://www.globalspec.com/reference/55806/203279/chapter-9-additional-circuit-designs https://www.globalspec.com/reference/55806/203279/chapter-9-...
ithkuil 3y ago
What does "full value" means in ia64? The register is filled with zeros?
- hcs 3y ago
  I wondered that, too, I think it means that the full value is used as the shift amount rather than modulo whatever. Which should mean that it'd end up filled with zeroes if shifting greater than the reg width.
notorandit 3y ago
Provided that you can actually do it, it depends upon whether you are doing signed shifts or not and whether you are doing left or right.
mannyv 3y ago
At least on 68k, the behavior is defined. http://www.tigernt.com/onlineDoc/68000.pdf http://www.tigernt.com/onlineDoc/68000.pdf I suppose the point is the behavior undefined in C/C++, so you have to look at the chip level doc to see...or test it yourself.

100 points by signa11 3y ago

What about if you rotate a register by more than the register size? Does it just rotate a few laps around the register unnecessarily? Does it optimize? Does it not work?

kevin_thibedeau 3y ago
Barrel rotators will just take the lower n-bits they need to perform a full word rotation. Extras are ignored as it's a modular operation.

Aardwolf 3y ago

> On the 8086, the shift amount is given by the 8-bit cl register. The running time of the instruction is proportional to the number of bits shifted, and the processor does not optimize shifts that are larger than the register size, so if you ask to shift by 255 places, it will run a loop 255 times. Wasn't this also the case on Pentium 4 (with different max value than 255), when they removed the barrel shifter?

adrian_b 3y ago
No. On all Intel and AMD CPUs starting with 80186 and 80286 (which have been launched simultaneously) only the lowest 5 (or 6 for 64-bit operations) bits of the shift value are used. All the other bits are ignored. It does not matter how the shift operation is implemented, with a barrel shifter or without it. The implementation influences only the execution time of the instruction, not its effects. This difference in the behavior of the shift and rotate operations was used by many programs to identify whether they were executed on an 8086/8088 or on an 80186/80188 (or a later) CPU. This was important, because 80186 had introduced some new useful instructions, and the standard means of detecting CPU features with the CPUID instruction has been introduced only more than a decade later, in Intel Pentium (1993). The detection of the CPU was based on the fact that shifting left a 16-bit register by 32 will not change it on an 80186 or later CPU, but it will produce the result zero on an 8086/8088.
ack_complete 3y ago
No, shifts were slow on the Pentium 4 but still constant timing regardless of shift distance, and they weren't microcoded.

deleted 3y ago

[deleted]

dgellow 3y ago

I said it multiple times over the years but Raymond Chen has been my favorite technical author for the past 10+ years and is always such a pleasure to read. Little anecdotes and pieces of history that make you think and dig more into various topics.

intelVISA 3y ago
[flagged]
- pavlov 3y ago
  Did this comment fall out of a 1995 time warp?
- dgellow 3y ago
  Strange thing to comment. He’s there since decades (92? I remember him mentioning a date beginning 90s on a C++ podcast episode) and seems to be I pretty good at his job. It’s clear he’s there because he wants to.
bombcar 3y ago
Every single one of his posts is posted from a place of pain, it's pretty obvious. So some horrible bug involving shifting registers ate a portion of his life, and we get a cool blog post.
- dgellow 3y ago
  Now that you say this, I really appreciate his writing style doesn’t project frustration. He has his way to make me curious about some weirdly technically specific errors, bugs, misconceptions without ranting or complaining. It always feels like a friend shared a nice little thing they would have learned the hard way over the years.
nanoxide 3y ago
I just wish there weren't so many rather C++ focused posts. The last few months weren't really that interesting for me. I get that there's a limited amount of fun Windows stuff and anecdotes, but these deep dives into Windows API C++ intricacies don't really fit his usual topics

ot 3y ago

I used to do a lot of bit twiddling (for compression) and the fact that shift values of 64 (for 64-bit integers) always have to be special-cased, instead of just zeroing out the value, is so annoying and inefficient. I really wish it just worked in hardware.

IshKebab 3y ago
I totally agree. I can understand why they don't allow it but it definitely makes code more awkward.
- thrtythreeforty 3y ago
  It would be about 64 gates. Sort of irritating that it doesn't work, to be honest.
jleahy 3y ago
Well it does work in hardware, but not with the normal shift instruction. Just use a ‘double shift’ which you can get with __int128 (or with inline asm, or just full asm).

nkurz 3y ago

Since it hasn't been mentioned yet, I'll point out that the article is about how hardware processors react to assembly level shifts with greater than register size. Unless you are programming directly in assembly, the most important take-home from the article is probably the "Bonus chatter" at the end: shifts equal to or greater than register size are undefined in C and C++. How the CPU would handle the theoretical assembly instruction is usually of little importance when demons are flying out of your nose. Here's Regehr on some of the standard ways to protect yourself from a malicious or overzealous compiler when you need to have a function that does variable sized rotations: https://blog.regehr.org/archives/1063 https://blog.regehr.org/archives/1063

fao_ 3y ago
I mean, I feel a sane reading of the C Standard means reading "undefined" as "unspecified by the standard, but dependent on the trust and common sense of the compiler authors" -- which, you know, I don't know that that's any worse than "dependent on the trust and common sense of the npm package author" or "dependent on the trust and common sense of the rust cargo maintainer". Like, yes theoretically the compiler can do anything, but tangibly, coherently, most compilers deal with most UB in a sane way.
- loup-vaillant 3y ago
  > but tangibly, coherently, most compilers deal with most UB in a sane way. It depends. In some cases, really, no they do not. Compilers have been caught deleting security checks when they noticed that the only way to reach the error case was to trigger UB… and since "UB doesn't exist", the error case is considered dead, and the whole test is deleted. Sometimes this leads to remote code execution vulnerabilities, that if exploited could actually result in your hard drive being encrypted, or a keylogger being installed. UB is really, really scary.
  - bippihippi1 3y ago
    cite source?

orlp 3y ago

You can get well-defined behavior at 0 cost (for x86-64 and ARM64, which covers most everything not very obscure/embedded) on both GCC and LLVM by explicitly adding a modulo operator: uint32_t foo(uint32_t x, int s) { return x << (s % 32); } foo(unsigned int, int): shlx eax, edi, esi ret

Someone 3y ago
Is that well defined for foo(0x12345678, -1) ? I think that, in modern C -1 % 32 == -1 (% computes the remainder, not the modulo) it would try to compute x << -1 and AFAIK that’s undefined behavior. Even if it is well-defined, it possibly is not what you want. If you were to call foo(0x12345678, 32) I think the most logical result would be zero, but the code you give returns 0x12345678.
- dzaima 3y ago
  Yeah, to be well-defined it should be 's & 31', or use an unsigned type for s; compiler explorer comparing those under ubsan shows the original having the possibility of UB: https://godbolt.org/z/eT9q871bY https://godbolt.org/z/eT9q871bY
- orlp 3y ago
  You're right I was sloppy in defining s to be an int, it should've been an unsigned type. My point was more about getting consistent behavior across platforms at (most often) zero cost, not to support arbitrary negative shifts.

hasmanean 3y ago

If you’re shifting right, the behaviour ought to be Unsigned: should produce a zero Signed: should sign extend the leftmost bit, so it will either be 0 or -1 Shifting left should result in a 0.

kazinator 3y ago

Should be "by the register size or more" not "by more than the register size". Machine-specific behavior starts at register size, not beyond! That's why in C, the behavior is undefined.

dzaima 3y ago

Note that this is only for the direct shift instructions. Some other related instructions, and SIMD versions, might be different from the regular shifts on the same architecture. x86-64's 'bzhi' instruction (does 'a & ((1<<b) - 1)') uses mod 256 (and thus, if mod 32/64 was specified in C, compilers couldn't optimize to this). ARM NEON's SIMD shifts merge both left and right shift in one instruction (reads low 8 bits as a signed int, positive being left shift, and negative - right shift)

lifthrasiir 3y ago
> if mod 32/64 was specified in C, compilers couldn't optimize to this This reads a bit ambiguously, though the conclusion would be same. If C specification had that requirement, yeah, they have to do mod 32/64 every time integers with unknown bounds are used for `b`. But then Intel should have noticed this first and define LZHI to use mod 32/64 according to the operand, or make two versions of LZHI. If C code had that requirement, for example, by always using `a & ((1 << (b & 31)) - 1)` to avoid an UB, compilers indeed would not be able to optimize it into a single BZHI. But they can use AND+BZHI, and I think BZHI has only a half of throughput than AND in almost all supported processors, so an excess AND probably can't do much harm.
- dzaima 3y ago
  True, Intel could've been influenced if there was an expectation on the behavior of shifts. But I doubt they'd have made two versions, and we'd just be stuck with the less useful mod 32/64 one.

cvccvroomvroom 3y ago

Ah, the olden days of 8086. When xor ax, ax was faster than mov ax, 0 and so was xor ax, bx; xor bx, ax; xor ax, bx to swap instead of using a temporary. Some processors also have ror and rol instructions that accomplish shifting in the shifted out bits. 8086 also had rotate with carry flag: rcr and rcl. Aids implementing sign-extended shift right and arbitrary precision math.

Narishma 3y ago
> Ah, the olden days of 8086. When xor ax, ax was faster than mov ax, 0 That's still the case today, no?
- th3typh00n 3y ago
  Yes, for 32- and 64-bit registers. Most modern x86 CPUs has fast paths for 'xor reg, reg' which performs the zeroing using the register renaming mechanism instead of actually executing anything on the back-end. So the only cost is that of decoding the instruction.

rolph 3y ago

Barrel Shifter: https://en.wikipedia.org/wiki/Barrel_shifter https://en.wikipedia.org/wiki/Barrel_shifter also : https://www.geeksforgeeks.org/overflow-in-arithmetic-addition-in-binary-number-system/ https://www.geeksforgeeks.org/overflow-in-arithmetic-additio... https://www.globalspec.com/reference/55806/203279/chapter-9-additional-circuit-designs https://www.globalspec.com/reference/55806/203279/chapter-9-...

ithkuil 3y ago

What does "full value" means in ia64? The register is filled with zeros?

hcs 3y ago
I wondered that, too, I think it means that the full value is used as the shift amount rather than modulo whatever. Which should mean that it'd end up filled with zeroes if shifting greater than the reg width.

notorandit 3y ago

Provided that you can actually do it, it depends upon whether you are doing signed shifts or not and whether you are doing left or right.

mannyv 3y ago

At least on 68k, the behavior is defined. http://www.tigernt.com/onlineDoc/68000.pdf http://www.tigernt.com/onlineDoc/68000.pdf I suppose the point is the behavior undefined in C/C++, so you have to look at the chip level doc to see...or test it yourself.