141 replies to this topic

[PhiLho]

Doh, I made small experiments to improve Laszlo's code from #94937, then I re-read the top of this page, and see that Titan's code with Laszlo' suggestions is just the code I wrote...
I missed it because it wasn't as is in a code section.
So, for the record, here is my version:

toHex3(ByRef _data, _dataSize=0)
{
	s := _dataSize = 0 ? VarSetCapacity(_data) : _dataSize
	a := &_data
	f := A_FormatInteger
	SetFormat Integer, H
	VarSetCapacity(h, 5 * s)
	Loop %s%
		h .= *(a++) + 256
	StringReplace h, h, 0x1, , All
	SetFormat Integer, %f%
	Return h
}

Note: I wondered what was this 's' parameter in the original script, used in a cryptic way. Titan' style of ultra-short variable names, esoteric use of operators and lack of comments makes hard to understand his scripts. I wouldn't want to have to maintain his code... ;-)
Note that + 256 is faster than + 0x100...
I suppose I could write *a++ but I prefer with parentheses, which auto-document the evaluation order.

I updated my BinaryEncodingDecoding.ahk file with the following code:

/*
// Convert raw bytes stored in a variable to a string of hexa digit pairs.
// Convert either _byteNb bytes or, if null, the whole content of the variable.
//
// Return the number of converted bytes, or -1 if error (memory allocation)
*/
Bin2Hex(ByRef @hexString, ByRef @bin, _byteNb=0)
{
	local dataSize, dataAddress, granted, f

	; Get size of data
	dataSize := _byteNb < 1 ? VarSetCapacity(@bin) : _byteNb
	dataAddress := [email protected]
	; Make enough room (faster)
	granted := VarSetCapacity(@hexString, dataSize * 5)
	if (granted < dataSize * 5)
	{
		; Cannot allocate enough memory
		ErrorLevel = Mem=%granted%
		Return -1
	}
	f := A_FormatInteger
	SetFormat Integer, H
	Loop %dataSize%
	{
		@hexString .= *(dataAddress++) + 256
	}
	StringReplace @hexString, @hexString, 0x1, , All
	SetFormat Integer, %f%

	Return dataSize
}

Note that passing the result ByRef is much faster!
Demonstration:

SetBatchLines -1
Process, Priority, , R

file := RegExReplace(A_AhkPath, "i)AutoHotkey\.exe$", "license.txt")
FileRead b, %file%
b := b b b b b b b b b b

t1 := A_TickCount
Loop 10000
	F1(b)
t1 := A_TickCount - t1
t2 := A_TickCount
Loop 10000
	F2(b)
t2 := A_TickCount - t2

t3 := A_TickCount
Loop 10000
	x := F3(b)
t3 := A_TickCount - t3
t4 := A_TickCount
Loop 10000
	F4(x, b)
t4 := A_TickCount - t4

MsgBox 1: %t1% / 2: %t2% / 3: %t3% / 4: %t4%

F1(b)
{
	a := &b
	Return a
}
F2(ByRef @b)
{
	a := [email protected]	; Do a little something, to get non-zero result...
	Return a
}
F3(b)
{
	r := b
	Return r
}
F4(ByRef @r, ByRef @b)
{
	@r := @b
	Return
}

[PhiLho]

I also improved my reverse routine, Hex2Bin, by a factor of two!
Old code (incorrect, I parse all the data!):

/*
// Convert a string of hexa digit pairs to raw bytes stored in a variable.
// Convert either _byteNb bytes or, if null, the whole content of the variable.
//
// Return the number of converted bytes, or -1 if error (memory allocation)
*/
Hex2Bin(ByRef @bin, ByRef @hex, _byteNb=0)
{
	local dataSize, granted, dataAddress, x

	; Get size of data
	x := StrLen(@hex)
	dataSize := x // 2
	if (x = 0 or dataSize * 2 != x)
	{
		; Invalid string, empty or odd number of digits
		ErrorLevel = Param
		Return -1
	}
	If (_byteNb < 1 or _byteNb > dataSize)
	{
		_byteNb := dataSize
	}
	; Make enough room
	granted := VarSetCapacity(@bin, _byteNb, 0)
	if (granted < _byteNb)
	{
		; Cannot allocate enough memory
		ErrorLevel = Mem=%granted%
		Return -1
	}
	dataAddress := [email protected]

	Loop Parse, @hex
	{
		if (A_Index & 1 = 1)	; Odd
		{
			x := A_LoopField	; Odd digit
		}
		Else
		{
			; Concatenate previous x and even digit, converted to hex
			x := "0x" . x . A_LoopField
			; Store integer in memory
			DllCall("RtlFillMemory"
					, "UInt", dataAddress
					, "UInt", 1
					, "UChar", x)
			dataAddress++
		}
	}

	Return _byteNb
}

First optim (I give just the loop, the test and allocation code is the same):

Loop %_byteNb%
	{
		x := "0x" . SubStr(@hex, 1 + (A_Index - 1) * 2, 2)
		; Store integer in memory
		DllCall("RtlFillMemory"
				, "UInt", dataAddress++
				, "UInt", 1
				, "UChar", x)
	}

Last optim (costly in memory, like the new Bin2Hex):

Hex2Bin(ByRef @bin, ByRef @hex, _byteNb=0)
{
	local l, data, granted, dataAddress

	If (_byteNb < 1 or _byteNb > dataSize)
	{
		; Get size of data
		l := StrLen(@hex)
		_byteNb := l // 2
		if (l = 0 or _byteNb * 2 != l)
		{
			; Invalid string, empty or odd number of digits
			ErrorLevel = Param
			Return -1
		}
	}
	; Make enough room
	granted := VarSetCapacity(@bin, _byteNb, 0)
	if (granted < _byteNb)
	{
		; Cannot allocate enough memory
		ErrorLevel = Mem=%granted%
		Return -1
	}
	data := RegExReplace(@hex, "..", "0x$0!")
	StringLeft data, data, _byteNb * 5
	dataAddress := [email protected]

	Loop Parse, data, !
	{
		; Store integer in memory
		DllCall("RtlFillMemory"
				, "UInt", dataAddress++
				, "UInt", 1
				, "UChar", A_LoopField)
	}

	Return _byteNb
}

Times: 1: 3296 / 2: 2407 / 3: 1406

[polyethene]

here is my version

Well done! It's really fast.
A couple enhancements could be OR256 and prefix increment (no order = faster evaluation?).

Titan' style of ultra-short variable names

It's how its done in algebra... and I got a mechanics M1 exam in 10 days (I wonder how you managed).

... and lack of comments makes hard to understand his scripts.

With no comments you will develop a thorough understanding of the semantics, just like I did to an extent

[Laszlo]

@PhiLho: You missed also the speed measurements with the versions of the 2hex functions using h .= *(a++) + 256, StringReplace vs. h .= *(a++) and a complex RegExReplace. For every character of long strings +256 needs a slow interpreted addition, with string-to-number conversion, which is offset by the binary regular expression replacement, giving the later an advantage.

I decided not to constantly update my several hex conversion functions making use of the new AHK features, because they would need an update almost every other week. [(Apr 2005), (July 2005), (July 2005)] When AHK version 2 comes out, we could go back an update the most interesting v1 scripts.

[Laszlo]

We have also found that using ntdll.dll\RtlFillMemoryUlong speeds up memory filling significantly, by handling 4 bytes in each dll call. You could give it a try, too.

[PhiLho]

I though of that (actually of using RtlStoreUlonglong...) but I wasn't sure about memory alignment and managing last bytes.
It is obvious indeed that the DllCall in the Hex2Bin is the bottleneck.

[Laszlo]

I could not make the UlongLong version to work (it did not seem to be exported). I handled the first and last (partial) words separately, depending on the last two bits of the address and the length of the data. (I am not sure, though, if the '00' ending of an address really means word alignment.)

[PhiLho]

@PhiLho: You missed also the speed measurements with the versions of the 2hex functions using h .= *(a++) + 256, StringReplace vs. h .= *(a++) and a complex RegExReplace. For every character of long strings +256 needs a slow interpreted addition, with string-to-number conversion, which is offset by the binary regular expression replacement, giving the later an advantage.

Indeed, I didn't looked at this version, but on my computer, it is slightly slower than my version, even when passing h ByRef.

Bin2Hex: 531 / Titan's toHex: 672 / Idem ByRef: 656

[polyethene]

I combined PhiLho's use of ByRef variables, Laszlo's idea of StringReplace and my RegEx and concatenation method for the fastest possible binary-to-hex function:

toHex(ByRef data, ByRef hex) {
	size := VarSetCapacity(data)
	VarSetCapacity(hex, 4 * size + 259)
	address := &data
	f = %A_FormatInteger%
	SetFormat, Integer, H
	Loop, %size%
		hex .= *address++
	SetFormat, Integer, %f%
	hex := RegExReplace(hex, "0x(.)(?=0x|$)", "0$1")
	StringReplace, hex, hex, 0x, , A
}

Edit: added hex assignment to regex.

[Laszlo]

- Titan, why do you need the +259 in VarSetCapacity? Does 0 make it slower? Or +1? Does RegExReplace needs some extra room?
- A hypothesis: when you return a long string from a function, it gets computed AND copied to another variable, like to x in "x := f(y)". This copy step is not performed if the result is returned in a ByRef parameter, f(x,y), where the return variable already contains the computed string.
--- Could someone verify of disprove it?
--- If it is true, AHK could be optimized not to copy the result, but use the address (if any) of the variable or temporary storage, where the result ends up. I think Chris would give it a low priority, though, because saving the copy is not that significant and he can better spend his time on new features.

[polyethene]

- Titan, why do you need the +259 in VarSetCapacity?

It's an arbitrary value (10.0 ** 99) to prevent auto-expansion [citation needed].

AHK could be optimized not to copy the result, but use the address (if any) of the variable

I was also hoping for this; there is a landslide difference between ByRef vars and Return values.

[Laszlo]

- Titan, why do you need the +259 in VarSetCapacity?

It's an arbitrary value (10.0 ** 99) to prevent auto-expansion

You misunderstood the 10.0**99 quote. I meant that, because 10.0**99 is a valid number, more than 100 characters could be needed to represent valid *numbers*. It has nothing to do with allocating room for hex streams. In your script we know that each byte of data is replaced with "0x?" or "0x??", that is, the maximum length of hex is 4*size. Not a single byte more. If you find speed improvement with allocating more memory, it shows that AHK (RegExReplace) does something unexpected behind the scene.

there is a landslide difference between ByRef vars and Return values.

It is surprising. Could you post your measurements?

[SKAN]

AHK could be optimized not to copy the result, but use the address (if any) of the variable or temporary storage, where the result ends up.

That would very nice as we can return binary data too.. I like to have my FRead() ( a wrapper for binary Read ) to work as normal as any conventional function.. That is it should return the value.. It does not work without accepting a byref.

I think Chris would give it a low priority, though, because saving the copy is not that significant and he can better spend his time on new features.

@Titan: That is the fastest! 450ms for that 190kb file I had tested previously.

Also,
6393ms for a 2,359,350 size BMP file.
I tested now with Win98SE & just 64MB on my Sempron 1.4Ghz.

Thanks ..

[polyethene]

If you find speed improvement with allocating more memory, it shows that AHK (RegExReplace) does something unexpected behind the scene.

When I was testing the function +259 made no difference so I left it in. RegExReplace and all string commands stop at the first null byte so the extra capacity shouldn't affect performance.

It is surprising. Could you post your measurements?

I noticed it with previous versions of toHex() with and without ByRef parameters. Here is a dummy test script:

SetBatchLines, -1
Process, Priority, , R
i = 10000
t1 := A_TickCount
Loop, %i% {
	p1 := A_Index * 10
	r1 := fr(p1)
}
t2 := A_TickCount
Loop, %i% {
	p2 := A_Index * 10
	fb(p2, r2)
}
t3 := A_TickCount
MsgBox, % r1 == r2 ? t2 - t1 . "`n" . t3 - t2 : "Error"
fr(t) {
	VarSetCapacity(dots, t, 46)
	Return, dots . "..."
}
fb(ByRef t, ByRef var) {
	VarSetCapacity(dots, t, 46)
	var := dots . "..."
}

[Laszlo]

I came up with a similar test script for the measurements, and got surprising results:

tf := A_TickCount
x := f()
tf -= A_TickCount
tg := A_TickCount
g(z)
tg -= A_TickCount

MsgBox % "Return: " . -tf . "`nByRef: " . –tg ; 200 / 60 ms

f() {
   VarSetCapacity(x,50000000,120)
   Return x
}

g(ByRef x) {
   VarSetCapacity(x,50000000,120)
}

To allocate and fill 50MB memory with the character "x" takes about 60 ms. To copy it from the return place to a variable takes another 140 ms, more than twice as much, what is unexpectedly long. However, with "normal" variable sizes this extra copying time is small (3 ms at 1MB), so you should not notice any difference. But you did. It means that something else is also playing a role. But what?

Add a "Global" directive to the function f().

tf := A_TickCount
y := f()
tf -= A_TickCount
tg := A_TickCount
g(z)
tg -= A_TickCount

MsgBox % "Return: " . -tf . "`nByRef: " . -tg

f() {
   Global x
   VarSetCapacity(x,50000000,120)
   Return x
}

g(ByRef x) {
   VarSetCapacity(x,50000000,120)
}

The same results, so it is not Global vs. Local.

Also, setting up a global variable takes the same time as a ByRef parameter (no Return), so Globals can be used for speeding up scripts, too.

f() {
   Global x
   VarSetCapacity(x,50000000,120)
}

Return seems to be the bad guy.