www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - recursive template (first attempt)

reply akcom <CppCoder gmail.com> writes:
I apologize if this is an easily resolved problem, this is my first
attempt at writing a template function.  the objective of this function
is to mimic the behavior of the AP hash function, but as a template
function obviously.  Here is what I have so far:

uint aphash( ubyte []buf )
{
	uint hash;
	
	for ( uint i = 0; i < buf.length; i++ )
	{
		hash ^= ((i & 1) == 0) ?	(  (hash <<  7) ^ (buf[i]) ^ (hash >> 3)) :
									(~((hash << 11) ^ (buf[i]) ^ (hash >> 5)));
	}
	return hash;
}

template aphasht( T : ubyte [] )
{
	uint aphasht( T t )
	{
		uint result;
		static if ( t.length == 0 )
		{
			return 0;
		}
		static if ( t.length & 1 )
		{
			result = aphasht( t[1..$] );
			return (result << 7) ^ t[0] ^ (result >> 3);
		}
		else
		{
			result = aphasht( t[1..$] );
			return (result << 11) ^ t[0] ^ (result >> 5);
		}
	}
}

void test()
{
	static ubyte []str = [ 0x01, 0x02, 0x03, 0x03 ];
	writefln( "aphash(str) = %X", aphash( str ) );
	writefln( "aphasht(str) = %X", aphasht!(ubyte [])( str ) );
}


When I attempt to compile it, I get the following errors:

dmd -w -c main.d
main.d(49): expression ((t).length) == 0u does not evaluate to a boolean
main.d(53): expression ((t).length) & 1u does not evaluate to a boolean
main.d(70): template instance main.aphasht!(ubyte[]) error instantiating

Could someone please point out my mistake, and if there is a more
elegant way of completing this task, I'd appreciate some input on that
as well.

Regards,
Alex
Apr 19 2006
parent reply Ryan Steen <Ryan_member pathlink.com> writes:
In article <e26v01$2m8$1 digitaldaemon.com>, akcom says...


		static if ( t.length == 0 )
		static if ( t.length & 1 )
main.d(49): expression ((t).length) == 0u does not evaluate to a boolean
main.d(53): expression ((t).length) & 1u does not evaluate to a boolean


"It is an error if AssignExpression ... cannot be evaluated at compile time."
Apr 19 2006
parent reply akcom <CppCoder gmail.com> writes:
Ryan Steen wrote:

 In article <e26v01$2m8$1 digitaldaemon.com>, akcom says...
 
 

		static if ( t.length == 0 )
		static if ( t.length & 1 )
main.d(49): expression ((t).length) == 0u does not evaluate to a boolean
main.d(53): expression ((t).length) & 1u does not evaluate to a boolean


 
 
 "It is an error if AssignExpression ... cannot be evaluated at compile time."
 
 


why can't it be computed at compile time if I make "str" static/const?
Apr 20 2006
parent reply Don Clugston <dac nospam.com.au> writes:
akcom wrote:

 Ryan Steen wrote:

 In article <e26v01$2m8$1 digitaldaemon.com>, akcom says...



 		static if ( t.length == 0 )
 		static if ( t.length & 1 )
 main.d(49): expression ((t).length) == 0u does not evaluate to a boolean
 main.d(53): expression ((t).length) & 1u does not evaluate to a boolean


 "It is an error if AssignExpression ... cannot be evaluated at compile time."


 why can't it be computed at compile time if I make "str" static/const?


It's just because array literals are only supported at this time for 
strings. (Your code might work in DMD 2.0).

If you change the definitions to
const char [] str = x"01 02 03";

template aphasht( char [] T)
{
	const uint aphasht = ...
}
(changing returns to const aphasht).

it would work with

writefln( "aphasht(str) = %X", aphasht!(str ) );
Apr 20 2006
parent akcom <CppCoder gmail.com> writes:
Don Clugston wrote:

 akcom wrote:
 

 Ryan Steen wrote:


 In article <e26v01$2m8$1 digitaldaemon.com>, akcom says...



         static if ( t.length == 0 )
         static if ( t.length & 1 )
 main.d(49): expression ((t).length) == 0u does not evaluate to a
 boolean
 main.d(53): expression ((t).length) & 1u does not evaluate to a boolean



 "It is an error if AssignExpression ... cannot be evaluated at
 compile time."


 why can't it be computed at compile time if I make "str" static/const?


 
 
 It's just because array literals are only supported at this time for
 strings. (Your code might work in DMD 2.0).
 
 If you change the definitions to
 const char [] str = x"01 02 03";
 
 template aphasht( char [] T)
 {
     const uint aphasht = ...
 }
 (changing returns to const aphasht).
 
 it would work with
 
 writefln( "aphasht(str) = %X", aphasht!(str ) );


I finally got it working, but for some odd reason the templates gives
different results than the original function when the string being
processed has a length that is odd, any ideas?

uint aphash( char []buf )
{
	uint hash;
	
	hash = 0;
	for ( uint i = 0; i < buf.length; i++ )
	{
		hash ^= ((i & 1) == 0) ?	(  (hash <<  7) ^ (cast(ubyte)buf[i]) ^ (hash

 3)) :




									(~((hash << 11) ^ (cast(ubyte)buf[i]) ^ (hash >> 5)));
	}
	return hash;
}

template aphashT( char []s, uint lastHash = 0 )
{
	static if ( s.length == 0 )
	{
		const aphashT = lastHash;
	}
	else static if ( s.length & 1 )
	{
		const aphashT = aphashT!( s[1..$], lastHash ^ ~( (lastHash << 11) ^
cast(ubyte)(s[0]) ^ (lastHash >> 5) ) );
	}
	else
	{
		const aphashT = aphashT!( s[1..$], lastHash ^ ( (lastHash << 7) ^
cast(ubyte)(s[0]) ^ (lastHash >>3) ) );
	}
}

unittest
{
	assert( aphashT!( "aaa" ) == aphash( "aaa" ) ); //fails
	assert( aphashT!( "abcdefg12345" ) == aphash( "abcdefg12345" ) );
	assert( aphashT!( "rofl haxor" ) == aphash( "rofl haxor" ) );
	assert( aphashT!( "abc" ) == aphash( "abc" ) );
	assert( aphashT!( "hello world" ) == aphash( "hello world" ) ); //fails
}
Apr 20 2006