[HN Gopher] What happens when you shift a register by more than ...
___________________________________________________________________
What happens when you shift a register by more than the register
size?
Author : signa11
Score : 89 points
Date : 2023-09-07 22:39 UTC (2 days ago)
(HTM) web link (devblogs.microsoft.com)
(TXT) w3m dump (devblogs.microsoft.com)
| kazinator wrote:
| 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.
| dgellow wrote:
| 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.
| nanoxide wrote:
| 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
| canucker2016 wrote:
| Might be the only Microsoft dev to wear a jacket and tie to
| work (though he's given up the jacket recently), certainly the
| most well known for his formal dress code on the main Redmond
| campus - see https://www.youtube.com/watch?v=w6dmGyVkNKk
| intelVISA wrote:
| Aye, I think he's wasted at m$ as it seems he actually knows
| what he's talking about.
| pavlov wrote:
| Did this comment fall out of a 1995 time warp?
| dgellow wrote:
| 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 wrote:
| 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 wrote:
| 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.
| hasmanean wrote:
| 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.
| Aardwolf wrote:
| > 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?
| ack_complete wrote:
| No, shifts were slow on the Pentium 4 but still constant timing
| regardless of shift distance, and they weren't microcoded.
| adrian_b wrote:
| 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.
| cvccvroomvroom wrote:
| 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 wrote:
| > Ah, the olden days of 8086. When xor ax, ax was faster than
| mov ax, 0
|
| That's still the case today, no?
| th3typh00n wrote:
| 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.
| notorandit wrote:
| 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.
| rolph wrote:
| Barrel Shifter:
|
| https://en.wikipedia.org/wiki/Barrel_shifter
|
| also :
|
| https://www.geeksforgeeks.org/overflow-in-arithmetic-additio...
|
| https://www.globalspec.com/reference/55806/203279/chapter-9-...
| orlp wrote:
| 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 wrote:
| 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 wrote:
| 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
| ot wrote:
| 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.
| jleahy wrote:
| 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).
| IshKebab wrote:
| I totally agree. I can understand why they don't allow it but
| it definitely makes code more awkward.
| thrtythreeforty wrote:
| It would be about 64 gates. Sort of irritating that it
| doesn't work, to be honest.
| ithkuil wrote:
| What does "full value" means in ia64? The register is filled with
| zeros?
| hcs wrote:
| 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.
| nkurz wrote:
| 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
| fao_ wrote:
| 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.
| kibwen wrote:
| _> 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"_
|
| You don't need to rely on the trust and common sense of
| anyone in those cases, because oversized shifts aren't
| undefined behavior in Javascript or Rust. If C (or C++, or
| any other language) wants the same benefit, they can just say
| that it's not undefined behavior, and thereby require
| implementations to define the behavior somehow. And
| "backwards compatibility" isn't an excuse here: UB means
| that, currently, _anything_ can happen, so having the
| standard specify that one particular thing happens is an
| entirely backwards-compatible change.
| loup-vaillant wrote:
| > _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 wrote:
| cite source?
| dzaima wrote:
| Here's one case: https://godbolt.org/z/aM89Eqs3v - the 'p
| == NULL' check is gone. Not directly harmful if the null
| page is inaccessible (which it's gonna be for most user-
| space stuff), but if it's accessible, it's quite bad.
| (and, fwiw, there's -fno-delete-null-pointer-checks to
| stop the compilers from doing this)
|
| And another commonly mentioned one:
| https://godbolt.org/z/6bf17W1Ee
| maccard wrote:
| > 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.
|
| Have you got a link to a CVE of an RCE that was caused by
| UB being exploited by an optimizer?
|
| Im with you that UB is dangerous, but let's be honest in
| 98% of situations it's correct to assume that integer
| overflow can't happen, and that if you pass a pointer into
| a function and don't check it that the call site has
| checked it.
| loup-vaillant wrote:
| No link, but I do recall a CVE talking about a buffer
| overflow vulnerability that could be traced back to a
| bounds check being removed by the compiler because the
| only way to go out of bounds was to overflow a signed
| integer. _(Signed integer overflow is UB, and "UB does
| not exist", so the check was "dead".)_
| tedunangst wrote:
| The Linux kernel used to have lots of deref then null
| check bugs, but you could map memory at address zero,
| controlling what should have been kernel memory.
| userbinator wrote:
| _but tangibly, coherently, most compilers deal with most UB
| in a sane way._
|
| They used to, but unfortunately increasingly not so much now.
|
| (Since the most popular ones are open-source, we should
| theoretically have the power to change that.)
| fanf2 wrote:
| This is not true in fact or in practice.
|
| For example, a compiler can assume that a variable sized
| shift is in range, then use value range propagation to
| eliminate tests, which can be very confusing if you expect
| the shift to be implicitly & 63.
| zX41ZdbW wrote:
| There is an undefined behavior in the compiler and an undefined
| behavior in the CPU.
|
| For example, bsr/bsf instructions (count leading or trailing
| bits) have undefined behavior if the argument is zero. What I
| observed is that the CPU leaves the destination register
| unchanged in this case (but it can do something else according
| to the spec, for example - set it to zero).
|
| The compiler exposes these instructions for convenience as
| intrinsics __builtin_clz/__builtin_ctz, which consequently,
| have undefined behavior if the argument is zero. But you can
| use them directly as an optimization if you know in advance
| that the argument is non-zero:
| https://github.com/ClickHouse/ClickHouse/blob/c0a43df749c827...
| Findecanor wrote:
| `bsr` and `bsf` have "undefined" results on a zero argument
| in _Intel 's_ documentation. In _AMD 's_ documentation
| however, the destination is supposed to be "unchanged".
|
| What is unusual is that the 32-bit flavours of these
| instructions leave the upper 32 bits unchanged, whereas other
| 32-bit integer instructions write zeroes there even if the
| lower bits in the destination are unchanged. Perhaps Intel
| intends to make these instructions zero-extend in the future
| ... or does there exist _some_ processor (from Intel or
| someone else) that zero-extends?
| somat wrote:
| See this is where undefined got lost somewhere. As a layman
| undefined appears to mean a specific thing here. "undefined by
| the specification because it does whatever the hardware does"
| in this context it should never mean "can not happen because it
| is undefined by the specification". Heck, I don't think it
| should mean that in any context. whenever a thing is undefined,
| it is almost always because there is varying hardware that the
| specification is trying to accommodate.
| bitwize wrote:
| I believe that in the before times, "undefined behavior"
| meant something could be valid in certain contexts, and
| erroneous in others (as opposed to "implementation-defined"
| in which something sensible must be done but it's not clear
| exactly what). For example, null-pointer indirection has
| meaning if you're banging bits on the bare metal; it means
| fetch from (or store to) location 0. But most user-space
| programs on virtual-memory machines don't use location 0, so
| null is reserved as an invalid pointer/sentinel value. Many
| architectures for which C compilers exist trap if you try to
| access an address outside the bounds of an explicitly
| allocated buffer; the Symbolics Lisp machines had a C
| environment in which all pointers were "fat": they contained
| both a pointer to a Lisp object (typically a vector) and an
| offset from the beginning of that object. So the semantics of
| memory accesses in C are meant to accommodate those
| architectures as well as ones in which memory is assumed to
| be one big array of fixed-size integers and you can read or
| write wherever.
| [deleted]
| paulmd wrote:
| > in this context it should never mean "can not happen
| because it is undefined by the specification".
|
| Even worse, undefined behavior doesn't just mean "what
| happens next isn't defined by the specification", it _is_
| defined, and it's "anything the compiler wants to happen or
| that might make the compiler's life simpler or emit more
| efficient code". It 's not that there's _no rules_ about what
| might be emitted, it 's that the standard _does_ explicitly
| say what happens next. And what is specified is an unlimited
| pass to reorder or transform any input source code that
| performs this undefined operation, since it was nonsensical
| anyway.
|
| The "undefined" part is the thing _that you did_ , it's the
| input not the output. The compiler's output _is_ defined, and
| it's "the compiler can do whatever it wants ". And that's
| actually probably the only thing that could make the
| situation worse!
|
| It can return a NOP;RETURN; and continue executing code
| instead of throwing an exception, or generate any other
| output for this function that makes its life easier, without
| let or hindrance by ordering or visibility, or by any
| relation to the input source code, in a reign of terror that
| makes a smashing blog post. It is valid to emit fdisk because
| you aliased a variable in an unreasonable portion of the
| code. It is valid to return 1 or null or anything else
| immediately and without notice, regardless of how this
| affects your expected invariants about data safety or code
| behavior. Etc.
|
| this is, of course, a wildly terrible and terrifying decision
| to make and Ritchie was absolutely right about that. It's
| mostly only because compilers have stayed somewhat sane about
| the code they do emit that this hasn't all come crashing
| down, but, they get smarter every year.
| IvyMike wrote:
| This can still bite you.
|
| Because an aggressive compiler will probably do constant
| optimization.
|
| And the software guy who optimizes 1<<32 might have a
| different notion of what to do than guy designing the
| hardware would do.
|
| For example, the SUNW compiler sometime around the year 2000.
| As me how I know.
| mike_hock wrote:
| Thankfully, the standard has seen fit to specify what exactly
| "undefined" means so you're not left to arbitrarily interpret
| only the bare word "undefined" in some sort of "layman" way.
| hansvm wrote:
| Unthankfully, the definition is so vague as to be totally
| useless from a programming perspective. Avoid invoking UB,
| or all hell breaks loose. [0]
|
| Separately, I don't think their point was that they were
| speaking as a layman, but rather that the loose definition
| they gave is historically accurate, easier to reason about,
| and what a working programmer not versed in the nuances of
| UB would expect. The fact that UB has its current
| definition is indicative of "undefined [getting] lost
| somewhere."
|
| [0] https://kristerw.blogspot.com/2017/09/why-undefined-
| behavior...
| [deleted]
| Rexxar wrote:
| A lot of this "undefined behaviour" should have been
| "implementation defined" or "unspecified behaviour" in my
| opinion. I don't know why they chose "undefined behaviour" in
| this case. It was a long time ago, they probably weren't
| aware it would lead to such problems.
| sebazzz wrote:
| > undefined by the specification because it does whatever the
| hardware does
|
| No, that's called implementation defined, isn't it?
| ComputerGuru wrote:
| No, implementation defined refers to the _compiler_
| implementation, which wouldn't be the source of behavior
| here.
| kps wrote:
| When this comes up, I like to quote Dennis Ritchie on
| `noalias`: "the committee is planting timebombs that are sure
| to explode in people's faces"; "a license for the compiler to
| undertake aggressive optimizations that are completely legal
| by the committee's rules, but make hash of apparently safe
| programs", and consequently: "[It] must go. This is non-
| negotiable. [...] It negates every brave promise X3J11 ever
| made about codifying existing practices, preserving the
| existing body of code, and keeping (dare I say it?) 'the
| spirit of C.'"
|
| This is what 'undefined behavior' _turned out to be_ , so
| it's clear to me that the consequences of the definition were
| not understood at the time.
| marcosdumay wrote:
| On the original meaning, it was more because the actual
| result depended on what data you had, the value of your
| registers, what part of the processor pipeline encountered
| the problem, what other processes you had and what they were
| doing, and some other impossible to predict stuff.
|
| Also, a lot of it could easily be promoted to implementation
| dependent ( _this_ is what you are describing) at the 90 's
| without any problem.
|
| But, of course, the modern interpretation is complete
| bullshit.
| inetknght wrote:
| > _As a layman undefined appears to mean a specific thing
| here. "undefined by the specification because it does
| whatever the hardware does" in this context it should never
| mean "can not happen because it is undefined by the
| specification"._
|
| Actually, undefined means "undefined by the specification".
| It doesn't _matter_ what the hardware does. The specification
| allows the hardware to do whatever it wants. It 's perfectly
| valid to wipe your hard drive if you trigger undefined
| behavior.
| [deleted]
| dunham wrote:
| I also wouldn't expect "undefined" to be consistent within
| a single compiler implementation. The optimizer is free to
| make different instances behave differently.
| Someone wrote:
| A single compiler can even seem inconsistent.
|
| A conforming compiler is allowed to completely remove
| undefined behavior like this: if((n <<
| 64) == 0) { println("Hi!\n"); }
| if((n << 64) != 0) { println("Hi!\n");
| }
|
| If it were implementation-defined, it would have to
| compile it to the equivalent of
| println("Hi!\n");
| [deleted]
| almostnormal wrote:
| > 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++.
|
| The article claims UB only at greater but not at equal:
|
| > Bonus chatter: The wide variety of behavior when shifting by
| more than the register size is one of the reasons why the C and
| C++ languages leave undefined what happens when you shift by
| more than the bit width of the shifted type.
|
| If think your "equal to or greater" is correct, and the article
| is wrong. The reason might be that the instructions are defined
| up to including equal for many hardware.
|
| I remember checking one case that included equal as valid for
| only one of left/right shift and invalid for the other
| (left/right encoded in 5 bit signed).
| [deleted]
| Waterluvian wrote:
| 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 wrote:
| 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.
| dzaima wrote:
| 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)
___________________________________________________________________
(page generated 2023-09-09 23:01 UTC)