Thread overview
ldc -O leads to wrong results
Mar 09, 2015
salsa
Mar 10, 2015
Dan Olson
Mar 10, 2015
salsa
Mar 14, 2015
Dude
Mar 14, 2015
Kagamin
March 09, 2015
Recently I got stuck with this:
compiling following code with ldc -O generates code that doesn't do what I expect it to do. Compiling it without optimizations works fine. Does somebody have any idea what the problem might be? To reproduce the bug just compile and run once with 'ldc *.d' and once with 'ldc -O *.d'...

thanks for your help

module dcrypt.crypto.engines.Salsa20Engine;

	// LDC - the LLVM D compiler (0.15.1):
	//  based on DMD v2.066.1 and LLVM 3.5.0
	//
	// to reproduce bug: run once with inline disabled and once with inline enabled, compare results:
	//
	// causes wrong behaviour: ldmd ldc_inline_issue.d -O
	//
	public void main() {
		import std.stdio;

		uint[Salsa20Engine.STATE_SIZE] x;
		uint[Salsa20Engine.STATE_SIZE] input;

		input[0..2] = cast(const(uint[]))"abcdefgh";

		Salsa20Engine.salsaCore(20, input[], x[]);

		writeln(x);
	}

class Salsa20Engine {

	enum STATE_SIZE = 16;
	

	/**
	 * Salsa20 function
	 *
	 * Params:
	 * rounds = number of rounds (20 in default implementation)
	 * input = input data
	 * x = output buffer where keystream gets written to
	 */
	public static void salsaCore(in uint rounds, in uint[] input, uint[] x) pure nothrow @nogc
	in {
		assert(rounds % 2 == 0 || rounds > 0, "rounds must be a even number and > 0");
		assert(input.length == STATE_SIZE, "invalid input length");
		assert(x.length == STATE_SIZE, "x: invalid length");

	}
	body {

		x[] = input[];
		
		for (int i = rounds; i > 0; i -= 2)
		{
			x[ 4] ^= rotl((x[ 0]+x[12]), 7);
			x[ 8] ^= rotl((x[ 4]+x[ 0]), 9);
			x[12] ^= rotl((x[ 8]+x[ 4]),13);
			x[ 0] ^= rotl((x[12]+x[ 8]),18);
			x[ 9] ^= rotl((x[ 5]+x[ 1]), 7);
			x[13] ^= rotl((x[ 9]+x[ 5]), 9);
			x[ 1] ^= rotl((x[13]+x[ 9]),13);
			x[ 5] ^= rotl((x[ 1]+x[13]),18);
			x[14] ^= rotl((x[10]+x[ 6]), 7);
			x[ 2] ^= rotl((x[14]+x[10]), 9);
			x[ 6] ^= rotl((x[ 2]+x[14]),13);
			x[10] ^= rotl((x[ 6]+x[ 2]),18);
			x[ 3] ^= rotl((x[15]+x[11]), 7);
			x[ 7] ^= rotl((x[ 3]+x[15]), 9);
			x[11] ^= rotl((x[ 7]+x[ 3]),13);
			x[15] ^= rotl((x[11]+x[ 7]),18);
			x[ 1] ^= rotl((x[ 0]+x[ 3]), 7);
			x[ 2] ^= rotl((x[ 1]+x[ 0]), 9);
			x[ 3] ^= rotl((x[ 2]+x[ 1]),13);
			x[ 0] ^= rotl((x[ 3]+x[ 2]),18);
			x[ 6] ^= rotl((x[ 5]+x[ 4]), 7);
			x[ 7] ^= rotl((x[ 6]+x[ 5]), 9);
			x[ 4] ^= rotl((x[ 7]+x[ 6]),13);
			x[ 5] ^= rotl((x[ 4]+x[ 7]),18);
			x[11] ^= rotl((x[10]+x[ 9]), 7);
			x[ 8] ^= rotl((x[11]+x[10]), 9);
			x[ 9] ^= rotl((x[ 8]+x[11]),13);
			x[10] ^= rotl((x[ 9]+x[ 8]),18);
			x[12] ^= rotl((x[15]+x[14]), 7);
			x[13] ^= rotl((x[12]+x[15]), 9);
			x[14] ^= rotl((x[13]+x[12]),13);
			x[15] ^= rotl((x[14]+x[13]),18);
		}
		
		// element wise addition
		x[] += input[];
		
	}
	
	/**
	 * Rotate left
	 *
	 * Params:
	 * x = value to rotate
	 * y = amount to rotate x
	 *
	 * Returns:  rotated x
	 */
	final static T rotl(T)(T x, T y) pure nothrow @nogc
	{
		return (x << y) | (x >>> -y);
	}
}
March 10, 2015
"salsa" <salsa@salsa.com> writes:

> Recently I got stuck with this:
> compiling following code with ldc -O generates code that doesn't do
> what I expect it to do. Compiling it without optimizations works
> fine. Does somebody have any idea what the problem might be? To
> reproduce the bug just compile and run once with 'ldc *.d' and once
> with 'ldc -O *.d'...
>
> 			x[ 4] ^= rotl((x[ 0]+x[12]), 7);
...
> 	final static T rotl(T)(T x, T y) pure nothrow @nogc
> 	{
> 		return (x << y) | (x >>> -y);
> 	}

Hi salsa.

y is 7 so (x >>> -7) yields an unspecified value because shift is
negative (see TDPL 2.3.10 Shift Expression).  I think results are only
defined when shifting 0 to nbits-1.

Here is one way to get it to work with -O:

 	final static T rotl(T)(T x, uint y) pure nothrow @nogc
 	{
            enum nbits = T.sizeof*8;
            return (x << y) | (x >>> nbits-y);
 	}

-- 
Dan
March 10, 2015
Thanks for the response!
This solved the problem.
March 14, 2015
On Tuesday, 10 March 2015 at 05:35:59 UTC, Dan Olson wrote:
> "salsa" <salsa@salsa.com> writes:
>
>> Recently I got stuck with this:
>> compiling following code with ldc -O generates code that doesn't do
>> what I expect it to do. Compiling it without optimizations works
>> fine. Does somebody have any idea what the problem might be? To
>> reproduce the bug just compile and run once with 'ldc *.d' and once
>> with 'ldc -O *.d'...
>>
>> 			x[ 4] ^= rotl((x[ 0]+x[12]), 7);
> ...
>> 	final static T rotl(T)(T x, T y) pure nothrow @nogc
>> 	{
>> 		return (x << y) | (x >>> -y);
>> 	}
>
> Hi salsa.
>
> y is 7 so (x >>> -7) yields an unspecified value because shift is
> negative (see TDPL 2.3.10 Shift Expression).  I think results are only
> defined when shifting 0 to nbits-1.

Maybe this should be explicitly said in documentation:
http://dlang.org/expression.html#ShiftExpression

Btw. why this is not compile error on the first place?



March 14, 2015
On Saturday, 14 March 2015 at 07:02:51 UTC, Dude wrote:
> Btw. why this is not compile error on the first place?

It can't be compilation error, because the function doesn't see all values passed to it. It probably belongs to checked arithmetic, which is not done by default.