This is a long message, so TL;DR:
* Be careful to distinguish between LOGICAL shift right and ARITHMETIC shift right (assuming a twos-complement architecture). * Some of these machine-level operations are not natively available in "C89" (ANSI X3.159-1989) at the coder's level, although the compiler, the OS, and quite a number of associated libraries are likely to use them quite extensively internally. My understanding is that they can be emulated in Lua, although not as cheaply as directly executing native machine code. --------------------------------- Digging back through my assembly experience, I've generally seen several instructions, perhaps more common in the pre-RISC and pre-SIMD days: These all come from my early days, assuming a bit layout for bits 15 to bit 0 of a register, with the highest-value bit on the left: +-------------------------------------------------------------------------------+ | 15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | +-------------------------------------------------------------------------------+ Bit 0 is 2^0, i.e. 1, bit 1 is 2^1, (2) bit 2 is 2^2 (4), bit 3 is 2^4 (8), etc. Bit 15 is 2^15, i.e. 32768. where such a register is either: Unsigned: Bit 15 is added to bits 0..14, to allow values [0..65535]; or Signed: Bit 15 is a sign bit, with value 0 meaning "positive, and value "1" meaning "negative". This allows values [-32768..32767]. Okay, we have a 16-bit register, with one bit having two different possible meanings (the differentiation is spread through other instructions, such as "unsigned multiply" versus "signed multiply"). So, for number of bits "n", we have the main shift/rotate instructions: [I'll assume n = 3 in the following examples in the interests of brevity.] 1. Shift Left "n" bits. - Superficially the same as "multiply by 2^n", except for: 1. "n=3" high bits, e.g. 15, 14 and 13, are lost; and 2. Zeroes are shifted in from the left; 2. Some lower bit becomes bit 15 (e.g. bit 12 for n=3). If the register is a signed value, its sign may change. 3. If n is greater than 15, then the register becomes all zeroes. 2. LOGICAL Shift Right "n" bits. +-------------------------------------------------------------------------------+ 0 -> | 15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | -> (lost) +-------------------------------------------------------------------------------+ NOTE the term of the use "logical" to qualify "shift". - Mostly similar to the shift left case, except that zeroes are shifted in from the right, and lowest "n" bits are lost (shifted out to the right). 3. ARITHMETIC Shift Right "n" bits. +-------------------------------------------------------------------------------+ /--> | 15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | -> (lost) | +-------------------------------------------------------------------------------+ | | | v \-------/ - The ARITHMETIC is *almost* the same as the logical shift right... except for a crucial change: Instead of zeroes being shifted into bit 15, each shift step (for 1..n steps) sees bit 15 copied into bit 14. This means that positive values will remain positive, and negative values will remain negative. This is roughly equal an integer division by 2^n, although I'm not certain of the actual or desirable rounding properties (round to zero? to even? to odd?). 4. Rotate Left "n" bits. The rotate instructions differ from the the shifts, in that the shifts either insert zeroes at the "dominant" end of each step, or, in the case of the arithmetic shift right, insert a copy of bit 15 into bit 14 at each step. Rotates, however, simply take the value that would have been "bumped out" by the rotate (bit 15 in the Rotate Left case), and re-insert it in the lowest position (bit 0 in the Rotate Left case), and keeps doing this procedure n times. 5 Rotate Right "n" bits. Similar to Rotate Left, except that bit 0 is bumped out, and is re-inserted in bit 15, and this is repeated for n steps. Here's a schematic representation of "rotate right 1 bit": +-------------------------------------------------------------------------------+ | 15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | --\ +-------------------------------------------------------------------------------+ | ^ | | v \--------------------------------------------------------------------------------/ ------------------------------------------------ Hope that I haven't bored you guys too much. Three variations on the above notes: 1. I've used a 16-bit register, but the same can be used on other register sizes, depending on the architecture. Microcontrollers and smaller CPUs will have 8-bit registers; many machines will have 32-bit registers, and larger machines will have 64-bit or even 128-bit registers. The same general principles apply. 2. A slightly more tricky case comes along when you want to string together a series of individual registers into one "mega-register". In this case, the CPU has a "Carry" flag that indicates e.g. for an addition, when the result exceeds the size of the register (but the carry, posing as the highest bit, together with the register, gives the correct result). Since carry-inclusive functions are so common, instructions sets tend to cater to them specifically with a separate set of commands, e.g. "add with carry", "rotate right through carry", etc. Here's a schematic representation of "rotate left through carry, 1 bit": +-------------------------------------------------------------------------------+ +---+ | 15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | <-- | C | --\ +-------------------------------------------------------------------------------+ +---| ^ | | v | \------------------------------------------------------------------------------------------/ 3. Newer DSP, SIMD machines, with more sophisticated integer hardware, offer "saturation" arithmetic modes, where, if a result would exceed the maximum possible value for the register size, the register is instead set to its maximum value. ----------------------- Hope this helps, sur-behoffski (Brenton Hoff) Programmer, Grouse Software |
On 05/15/2017 03:31 AM, sur-behoffski wrote:
> This is a long message, so TL;DR: > > * Be careful to distinguish between LOGICAL shift right and ARITHMETIC > shift right (assuming a twos-complement architecture). > > * Some of these machine-level operations are not natively available in > "C89" (ANSI X3.159-1989) at the coder's level, although the > compiler, > the OS, and quite a number of associated libraries are likely to use > them quite extensively internally. My understanding is that they > can > be emulated in Lua, although not as cheaply as directly executing > native machine code. > Good post! I think it'll benefit from mentioning related Intel microprocessor instructions: operation | left | right -----------+------+------- shift | SHL | SHR .arithm | SAL | SAR rotate | ROL | ROR .via_carry| RCL | RCR -- Martin |
Free forum by Nabble | Edit this page |