xxHash conversion to Livecode
Moderators: FourthWorld, heatherlaine, Klaus, robinmiller
xxHash conversion to Livecode
I'm trying to build a Livecode implementation of the xxHash algorithm. Originally it's written in C but there have been built implementations in a lot of other languages and i'm using the C# version as a source because i understand the language better than plain C: https://github.com/noricube/xxHashSharp ... /xxHash.cs
The first problem i'm facing is that in this code the uint variable type (unsigned 32bit integer) is used and they also use a "feature" (which i always saw as a limitation) where if it reaches it's maximum value of 4,294,967,295 it will loop around. The problem i'm facing is that in LC i can't find a variable type which works this way because of the loose typing which is a good thing normally but not in this case.
For example, take the following which seems like a simple sum:
_state.v1 = seed + PRIME32_1 + PRIME32_2; // (seed = uint = 0, PRIME32_1 = uint = 2654435761, PRIME32_2 = uint = 2246822519)
In LC _state.v1 will have the value 4901258280 but in C# it will overflow at 4294967295 so it will have the value 606290985
Now my actual question: what is the best way to implement this in LC and mimick the way a uint works (also for subtraction)?
The first problem i'm facing is that in this code the uint variable type (unsigned 32bit integer) is used and they also use a "feature" (which i always saw as a limitation) where if it reaches it's maximum value of 4,294,967,295 it will loop around. The problem i'm facing is that in LC i can't find a variable type which works this way because of the loose typing which is a good thing normally but not in this case.
For example, take the following which seems like a simple sum:
_state.v1 = seed + PRIME32_1 + PRIME32_2; // (seed = uint = 0, PRIME32_1 = uint = 2654435761, PRIME32_2 = uint = 2246822519)
In LC _state.v1 will have the value 4901258280 but in C# it will overflow at 4294967295 so it will have the value 606290985
Now my actual question: what is the best way to implement this in LC and mimick the way a uint works (also for subtraction)?
-
- Livecode Opensource Backer
- Posts: 9454
- Joined: Fri Feb 19, 2010 10:17 am
- Location: Bulgaria
Re: xxHash conversion to Livecode
I understand nothing about this; but I did look up "uint"
in Livecode's built-in Dictionary.
in Livecode's built-in Dictionary.
-
- VIP Livecode Opensource Backer
- Posts: 9856
- Joined: Sat Apr 08, 2006 7:05 am
- Location: Los Angeles
- Contact:
Re: xxHash conversion to Livecode
Vince, might you have better luck implementing the 32-bit version of the xxHash algo?
Richard Gaskin
LiveCode development, training, and consulting services: Fourth World Systems
LiveCode Group on Facebook
LiveCode Group on LinkedIn
LiveCode development, training, and consulting services: Fourth World Systems
LiveCode Group on Facebook
LiveCode Group on LinkedIn
Re: xxHash conversion to Livecode
@Richmond62: for a moment I thought that I had missed a crucial LC command but unfortunately these commands don't do what I need...
@FourthWorld: to my knowledge this is the 32bit version.
@FourthWorld: to my knowledge this is the 32bit version.
Re: xxHash conversion to Livecode
Code: Select all
if (_state.v1 > 4294967295) then
_state.v1 = _state.v1- 4294967295
end if
-
- VIP Livecode Opensource Backer
- Posts: 2262
- Joined: Thu Feb 28, 2013 11:52 pm
- Location: Göttingen, DE
Re: xxHash conversion to Livecode
Hi 'shaosean'.
I came to LC after you were "gone" for a while. But I read a lot of your brilliant posts. Thus I like it very much that you are here again.
p.s. Why do you dislike "mod"?
I came to LC after you were "gone" for a while. But I read a lot of your brilliant posts. Thus I like it very much that you are here again.
p.s. Why do you dislike "mod"?
shiftLock happens
Re: xxHash conversion to Livecode
Yes, i guess something like that is what i have to do to get this working. I was hoping there would be a more elegant solution because this way it can get less efficient and a lot of extra code very quickly. I will have to cater for every type of interaction: add, substract, multiply, etc...shaosean wrote:Code: Select all
if (_state.v1 > 4294967295) then _state.v1 = _state.v1- 4294967295 end if
PS: for the add i would resort to a "mod" call so it will work fine even if it would overflow several times.
Thanks all!
-
- VIP Livecode Opensource Backer
- Posts: 2262
- Joined: Thu Feb 28, 2013 11:52 pm
- Location: Göttingen, DE
Re: xxHash conversion to Livecode
"a mod b" works also for *negative* numbers a. Only the divisor b has to be positive (as you need it).
== "if (_state.v1 > 4294967295)" is not slower than "(_state.v1 mod 4294967295)"
Two ideas:
== You could also think about an implementation of python's "bignum" package?
== You could think about using log2?
[As this is a very fast algorithm: Do you plan to share your LC-implementation?]
== "if (_state.v1 > 4294967295)" is not slower than "(_state.v1 mod 4294967295)"
Two ideas:
== You could also think about an implementation of python's "bignum" package?
== You could think about using log2?
[As this is a very fast algorithm: Do you plan to share your LC-implementation?]
Last edited by [-hh] on Tue Jul 19, 2016 10:26 pm, edited 2 times in total.
shiftLock happens
Re: xxHash conversion to Livecode
Thanks.[-hh] wrote:"a mod b" works also for *negative* numbers a. Only the divisor b has to be positive (as you need it).
You could also think about an implementation of python's "bignum" package.
[As this is a very fast algorithm: Do you plan to share your LC-implementation?]
If i manage to translate xxHash to LC i might share it. Something tells me that the best way to do it would be to use LC builder/studio but this is very new to me and seems more complicated to do. I selected xxHash because of it's speed/quality and because i need to hash potentially very big files while i am copying them (50GB and larger). So for this to work i will have to continuously "stream" my data through the hashing function and not perform the hash like md5Digest does.
-
- VIP Livecode Opensource Backer
- Posts: 2262
- Joined: Thu Feb 28, 2013 11:52 pm
- Location: Göttingen, DE
Re: xxHash conversion to Livecode
This is by far too much for an interpreter, you will probably need a native procedure, that is, if using LiveCode, an external or a FFI (there is even a very fast LuaJIT implementation https://github.com/szensk/luaxxhash ).vince wrote:need to hash potentially very big files while i am copying them (50GB and larger)
Last edited by [-hh] on Tue Jul 19, 2016 10:20 pm, edited 1 time in total.
shiftLock happens
-
- VIP Livecode Opensource Backer
- Posts: 9856
- Joined: Sat Apr 08, 2006 7:05 am
- Location: Los Angeles
- Contact:
Re: xxHash conversion to Livecode
Yes, I saw that in your OP, but the sample code uses a ulong and the LC version needs to handle numbers larger than 4 bytes can accommodate. Looks like shaosean's got you covered (good to see you here again, shaosean).vince wrote:@FourthWorld: to my knowledge this is the 32bit version.
Richard Gaskin
LiveCode development, training, and consulting services: Fourth World Systems
LiveCode Group on Facebook
LiveCode Group on LinkedIn
LiveCode development, training, and consulting services: Fourth World Systems
LiveCode Group on Facebook
LiveCode Group on LinkedIn
Re: xxHash conversion to Livecode
I will have to find out if it is too much. To me it seems you call Init once at the start, after that you stream your data through the Update function which will contiuously update the hash counters with a not too complex calculation and at the end calculate/call the Digest function to obtain the hash. By doing it this way i think it should be possible even from pure LC.[-hh] wrote:This is by far too much for an interpreter, you will probably need a native procedure, that is, if using LiveCode, an external or a FFI.
But i'm by no means an expert, just someone with a challenge to keep me busy
Re: xxHash conversion to Livecode
I have seen this, is this something i could easily interface from within LC? (not knowing Lua / LuaJIT at all and how it relates to LC)[-hh] wrote:...there is even a very fast LuaJIT implementation https://github.com/szensk/luaxxhash ).
(But a downside of that LuaJIT implementation is that it doesn't implement the update/digest way of calculating the hash which is what i need)
-
- VIP Livecode Opensource Backer
- Posts: 2262
- Joined: Thu Feb 28, 2013 11:52 pm
- Location: Göttingen, DE
Re: xxHash conversion to Livecode
There are other xxHash-LuaJIT-implementations cited there (one very fast, that uses C-bindings).
LuaJIT is, being mostly written in Assembler, for a lot of 'basic' procedures even faster than C. You can use it via LC's "shell" handler.
An example for using LC as a GUI to LuaJIT is here (imageJIT -- beta version)
http://forums.livecode.com/viewtopic.ph ... 32#p143932
LuaJIT is, being mostly written in Assembler, for a lot of 'basic' procedures even faster than C. You can use it via LC's "shell" handler.
An example for using LC as a GUI to LuaJIT is here (imageJIT -- beta version)
http://forums.livecode.com/viewtopic.ph ... 32#p143932
shiftLock happens
Re: xxHash conversion to Livecode
Thanks -hh, you have given me good ideas!
I have now built a small test with LuaJIT and xxHash and it performs hash calculations at the speed of the copy while using < 1% CPU! For example i hashed a 25GB file in under a minute from my internal SSD.
Based on these results i now think it is better to use LuaJIT in combination with LC and interface it with "open process". This also has the advantage that it creates a seperate process which frees the main LC program of the i/o intensive data transfer handling.
I have now built a small test with LuaJIT and xxHash and it performs hash calculations at the speed of the copy while using < 1% CPU! For example i hashed a 25GB file in under a minute from my internal SSD.
Based on these results i now think it is better to use LuaJIT in combination with LC and interface it with "open process". This also has the advantage that it creates a seperate process which frees the main LC program of the i/o intensive data transfer handling.