Right Shift - Revision history

ObviousAltIsObvious Resident: tag to

2015-01-25T00:46:04Z

← Older revision		Revision as of 17:46, 24 January 2015
Line 13:		Line 13:
	=== Method 1 ===		=== Method 1 ===
	This method is good when count is dynamic (not known at compile time) but is twice as complicated as Method 2.		This method is good when count is dynamic (not known at compile time) but is twice as complicated as Method 2.
	<~~lsl~~>((value & 0x7fFFffFF) >> count) - ((value & 0x80000000) >> count);</~~lsl~~>		<source lang="lsl2">((value & 0x7fFFffFF) >> count) - ((value & 0x80000000) >> count);</source>
	This works by shifting body and sign bits separately and then recombining them. Since the sign bit is extended as a negative number, we just need to make it positive. Since the left and right values have no bits in common (due to the masking), we can use \| or + and they will do the same thing. To simplify the code we merge the negation and combine into a single operation.		This works by shifting body and sign bits separately and then recombining them. Since the sign bit is extended as a negative number, we just need to make it positive. Since the left and right values have no bits in common (due to the masking), we can use \| or + and they will do the same thing. To simplify the code we merge the negation and combine into a single operation.

	=== Method 2 ===		=== Method 2 ===
	This method can only be used when count is a constant value. It works by using a constant mask to remove the extended sign bits.		This method can only be used when count is a constant value. It works by using a constant mask to remove the extended sign bits.
	<~~lsl~~>(value >> count) & mask;</~~lsl~~>		<source lang="lsl2">(value >> count) & mask;</source>
	'''Example:''' <code>(value >> 5) & 0x07FFFFFF</code><br>		'''Example:''' <code>(value >> 5) & 0x07FFFFFF</code><br>
	As you can see the top five bits have been turned off in the mask value, if you have trouble seeing that, you can just use the lookup table below.		As you can see the top five bits have been turned off in the mask value, if you have trouble seeing that, you can just use the lookup table below.
Line 183:		Line 183:
	Here's a function that encapsulates the first method. It allows for a signed 32 bit integer along with a value indicating how far to shift the bits to be executed as an unsigned right shift.		Here's a function that encapsulates the first method. It allows for a signed 32 bit integer along with a value indicating how far to shift the bits to be executed as an unsigned right shift.

	<~~lsl~~>// the lsl right shift is an arithmetic right shift,		<source lang="lsl2">// the lsl right shift is an arithmetic right shift,
	// this means it more closely resembles dividing by a		// this means it more closely resembles dividing by a
	// positive power of two then a unsigned right shift.		// positive power of two then a unsigned right shift.
Line 207:		Line 207:
	//to inline due to the condition, not to mention the cost of forking.		//to inline due to the condition, not to mention the cost of forking.
	}		}
	</~~lsl~~>		</source>
	'''Example Usage:'''		'''Example Usage:'''
	<~~lsl~~>default		<source lang="lsl2">default
	{		{
	state_entry()		state_entry()
Line 219:		Line 219:
	// after: 0000 1111 1111 1111 1111 1111 1111 1001		// after: 0000 1111 1111 1111 1111 1111 1111 1001
	}		}
	}</~~lsl~~>		}</source>

	{{LSLC\|Examples\|Right Shift}}		{{LSLC\|Examples\|Right Shift}}
	[[Category: LSL Encryption]]		[[Category: LSL Encryption]]

Strife Onizuka: modulo is more expensive than bit-and, gives the same result in this case

2011-11-23T19:38:08Z

modulo is more expensive than bit-and, gives the same result in this case

← Older revision		Revision as of 12:38, 23 November 2011
Line 3:		Line 3:
	== Unsigned vs. Arithmetic ==		== Unsigned vs. Arithmetic ==

	There are two types of Right Shifts, that can be performed on an integer. They are: Unsigned and Arithmetic. LSL currently only supports Arithmetic. The difference between the two modes is how it fills the bits revealed. With the unsigned mode, the revealed bits are always zero; in Arithmetic mode, it duplicates the old top bit to all the new bits. If you take the expression <code>value >> count</code> where ''value'' is arithmetically shifted right ''count'' bits, then this is the same mathematically as doing <code>value / (2<sup>count</sup>)</code> or in LSL <code>value / [[llPow]](2.0, count)</code>.		There are two types of Right Shifts, that can be performed on an integer. They are: Unsigned and Arithmetic. LSL currently only supports Arithmetic. The difference between the two modes is how it fills the bits revealed. With the unsigned mode, the revealed bits are always zero; in Arithmetic mode, it duplicates the old top bit to all the new bits. If you take the expression <code>value >> count</code> where ''value'' is arithmetically shifted right ''count'' bits, then this is the same mathematically as doing <code>value / (2<sup>count</sup>)</code> or in LSL <code>value / [[llPow]](2.0, count)</code> (but will result in data loss in LSL).

	== How to do Unsigned Right Shifts in LSL ==		== How to do Unsigned Right Shifts in LSL ==
Line 12:		Line 12:

	=== Method 1 ===		=== Method 1 ===
	<lsl>(value >> count) ~~& ~~~((~value) >> count);</lsl>		This method is good when count is dynamic (not known at compile time) but is twice as complicated as Method 2.
	This ~~method~~ is ~~good when count is dynamic~~.		<lsl>((value & 0x7fFFffFF) >> count) - ((value & 0x80000000) >> count);</lsl>
	~~It works because all~~ the bits ~~that need~~ to ~~be turned on will be turned on both sides of~~ the ~~AND but on only one side~~ will the ~~arithmetic right shift cause~~ the ~~sign bit to be extended. The result of~~ the and is a ~~value that is always a unsigned right shift.~~		This works by shifting body and sign bits separately and then recombining them. Since the sign bit is extended as a negative number, we just need to make it positive. Since the left and right values have no bits in common (due to the masking), we can use \| or + and they will do the same thing. To simplify the code we merge the negation and combine into a single operation.

	~~The method above doesn't work~~.

	~~<lsl>~~
	~~// Jonhboy Resident 2011/11/20~~
	~~integer rightShift(integer value, integer count) {~~

	~~if(count%32) return ~(0x80000000 >> (count - 1)) & (value >> count); return value;~~
	~~}</lsl>~~

	=== Method 2 ===		=== Method 2 ===
			This method can only be used when count is a constant value. It works by using a constant mask to remove the extended sign bits.
	<lsl>(value >> count) & mask;</lsl>		<lsl>(value >> count) & mask;</lsl>
	~~This method can only be used when count is a constant value. You use a constant mask to remove the extended sign bits.~~ Example: <code>(value >> 5) & 0x07FFFFFF</code> As you can see the top five bits have been turned off in the mask value, if you have trouble seeing that, you can just use the lookup table below.		'''Example:''' <code>(value >> 5) & 0x07FFFFFF</code><br>
			As you can see the top five bits have been turned off in the mask value, if you have trouble seeing that, you can just use the lookup table below.

	{\|		{\|
Line 196:		Line 189:
	integer rightShift(integer value, integer count)		integer rightShift(integer value, integer count)
	{		{
	return (value >> count) ~~& ~~~((~value) >> count);		return ((value & 0x7fFFffFF) >> count) - ((value & 0x80000000) >> count);
	//This works ~~because only once side of the '&' operation~~		//This works by shifting body and sign bits separately and then
	//~~Has~~ the sign bit extended by the ~~arithmetic right shift~~		//recombining them. Since the sign bit is extended as a negative
	//~~The purpose of flipping of the~~ bits on the ~~right side~~		//number, we just need to make it positive. Since the left and
	//~~ensures this,~~ the ~~subsequent '&' removes~~ the ~~extended~~		//right values have no bits in common (due to the masking), we
	//~~sign bits~~.		//can use \| or + and they will do the same thing. To simplify the
			//code we merge the negation and combine into a single operation.
	}		}

	// Jonhboy Resident		// Jonhboy Resident
	integer ~~rightShiftCorrect~~(integer value, integer count) {		integer rightShiftJonhboy(integer value, integer count) {
			if(count & 31)
	if(count~~%32~~) return ~(0x80000000 >> (count - 1)) & (value >> count); return value;		return ~(0x80000000 >> (count - 1)) & (value >> count);
			return value;
			//This works by conditionally applying a calculated mask after
			//shifting. The disadvantage of this method is that it is hard
			//to inline due to the condition, not to mention the cost of forking.
	}		}
	</lsl>		</lsl>
Line 215:		Line 213:
	state_entry()		state_entry()
	{		{

	// output should be 268435449		// output should be 268435449
	llSay(DEBUG_CHANNEL, (string)rightShift(-99, 4)); // output: -7		llSay(DEBUG_CHANNEL, (string)rightShift(-99, 4)); // output: 268435449
	llSay(DEBUG_CHANNEL, (string)~~rightShiftCorrect~~(-99, 4)); // output: 268435449		llSay(DEBUG_CHANNEL, (string)rightShiftJonhboy(-99, 4)); // output: 268435449
	// before: 1111 1111 1111 1111 1111 1111 1001 1101		// before: 1111 1111 1111 1111 1111 1111 1001 1101
	// after: 0000 1111 1111 1111 1111 1111 1111 1001		// after: 0000 1111 1111 1111 1111 1111 1111 1001

Strife Onizuka: doesn't work in LSLEditor (different execution order)

2011-11-23T18:48:21Z

doesn't work in LSLEditor (different execution order)

← Older revision		Revision as of 11:48, 23 November 2011
Line 22:		Line 22:
	integer rightShift(integer value, integer count) {		integer rightShift(integer value, integer count) {

	if(count%32) return ~(0x80000000 >> -~~-count~~) & (value >> count); return value;		if(count%32) return ~(0x80000000 >> (count - 1)) & (value >> count); return value;
	}</lsl>		}</lsl>

Line 207:		Line 207:
	integer rightShiftCorrect(integer value, integer count) {		integer rightShiftCorrect(integer value, integer count) {

	if(count%32) return ~(0x80000000 >> -~~-count~~) & (value >> count); return value;		if(count%32) return ~(0x80000000 >> (count - 1)) & (value >> count); return value;
	}		}
	</lsl>		</lsl>

Jonhboy Resident: /* Example Unsigned Right Shift Function */

2011-11-20T15:15:05Z

Example Unsigned Right Shift Function

← Older revision		Revision as of 08:15, 20 November 2011
Line 217:		Line 217:

	// output should be 268435449		// output should be 268435449
	llSay(DEBUG_CHANNEL, (string)rightShift(-99, 4)); // output:-7		llSay(DEBUG_CHANNEL, (string)rightShift(-99, 4)); // output: -7
	llSay(DEBUG_CHANNEL, (string)rightShiftCorrect(-99, 4)); // output: 268435449		llSay(DEBUG_CHANNEL, (string)rightShiftCorrect(-99, 4)); // output: 268435449
	// before: 1111 1111 1111 1111 1111 1111 1001 1101		// before: 1111 1111 1111 1111 1111 1111 1001 1101

Jonhboy Resident: /* Example Unsigned Right Shift Function */

2011-11-20T15:14:47Z

Example Unsigned Right Shift Function

← Older revision		Revision as of 08:14, 20 November 2011
Line 217:		Line 217:

	// output should be 268435449		// output should be 268435449
	llSay(DEBUG_CHANNEL, (string)rightShift(-99, 4)); // output :-7		llSay(DEBUG_CHANNEL, (string)rightShift(-99, 4)); // output:-7
	llSay(DEBUG_CHANNEL, (string)rightShiftCorrect(-99, 4)); // output : 268435449		llSay(DEBUG_CHANNEL, (string)rightShiftCorrect(-99, 4)); // output: 268435449
	// before: 1111 1111 1111 1111 1111 1111 1001 1101		// before: 1111 1111 1111 1111 1111 1111 1001 1101
	// after: 0000 1111 1111 1111 1111 1111 1111 1001		// after: 0000 1111 1111 1111 1111 1111 1111 1001

Jonhboy Resident: /* Method 1 */

2011-11-20T15:12:21Z

Method 1

← Older revision		Revision as of 08:12, 20 November 2011
Line 19:		Line 19:

	<lsl>		<lsl>
	// Jonhboy Resident 20/11/~~2011~~		// Jonhboy Resident 2011/11/20
	integer rightShift(integer value, integer count) {		integer rightShift(integer value, integer count) {

Jonhboy Resident: /* Method 1 */

2011-11-20T15:11:38Z

Method 1

← Older revision		Revision as of 08:11, 20 November 2011
Line 19:		Line 19:

	<lsl>		<lsl>
	// Jonhboy Resident		// Jonhboy Resident 20/11/2011
	integer rightShift(integer value, integer count) {		integer rightShift(integer value, integer count) {

Jonhboy Resident: /* Method 1 */

2011-11-20T15:11:22Z

Method 1

← Older revision		Revision as of 08:11, 20 November 2011
Line 20:		Line 20:
	<lsl>		<lsl>
	// Jonhboy Resident		// Jonhboy Resident
			integer rightShift(integer value, integer count) {

	~~integer rightShift(integer value, integer count) {~~
	if(count%32) return ~(0x80000000 >> --count) & (value >> count); return value;		if(count%32) return ~(0x80000000 >> --count) & (value >> count); return value;
	}</lsl>		}</lsl>

Jonhboy Resident: /* Method 1 */

2011-11-20T15:11:00Z

Method 1

← Older revision		Revision as of 08:11, 20 November 2011
Line 22:		Line 22:

	integer rightShift(integer value, integer count) {		integer rightShift(integer value, integer count) {

	if(count%32) return ~(0x80000000 >> --count) & (value >> count); return value;		if(count%32) return ~(0x80000000 >> --count) & (value >> count); return value;
	}</lsl>		}</lsl>

Jonhboy Resident: /* Example Unsigned Right Shift Function */

2011-11-20T15:09:06Z

Example Unsigned Right Shift Function

← Older revision		Revision as of 08:09, 20 November 2011
Line 203:		Line 203:
	//ensures this, the subsequent '&' removes the extended		//ensures this, the subsequent '&' removes the extended
	//sign bits.		//sign bits.
			}

	// Jonhboy Resident		// Jonhboy Resident

	integer rightShiftCorrect(integer value, integer count) {		integer rightShiftCorrect(integer value, integer count) {

	if(count%32) return ~(0x80000000 >> --count) & (value >> count); return value;		if(count%32) return ~(0x80000000 >> --count) & (value >> count); return value;
	}		}
			</lsl>
	}</lsl>
	'''Example Usage:'''		'''Example Usage:'''
	<lsl>default		<lsl>default