In regards to my guesstimation: Of course it is not accurate... it's in the word. My way of thinking: A new graphics card simply delivers 2-3x more performance than my graphics card. There are AES implementations which are ~2x more performant than mine. I believe this is my first OpenCL code and therefore probably not as good as it gets... a further 2x may be possible here just by how you deploy the workload onto the graphics card. 2-3x * ~2x * 2x = 10x.

In regards to the lookuptable: You have ~250.000x 4KB (let's call them:) cache entrys. With the lookup table you have to calculate every cache entry once (256k calculations), which involves generating 64 SHA512 hashes per cache entry. If you calculate them on-the-fly, you have to calculate every cache entry (very worst case:) 16 times. Now that seems like a bad number at first, because it would take 16 times as long to calculate these cache entrys, but you have to put it in context! Or more specifically: what would be the overall performance decrease?

One way of doing it is mathematically, in which case you would compare
versus
Now the question is how expensive is that SHA512 compared to the AES CBC?

So instead I do it the other way... I implemented both algorithms (with and without Scratchpad) and these are the results I am measuring on CPU:
versus

So the penalty hit for not using a 1GB lookup table is 70% in this scenario! And this leaves things out like the fact, that the SHA-512 step has much more optimizations/parallelization possible than a AES-CBC, which would decrease the relative performance hit you would take, after optimization.
You end up with this trade off: Use 1GB of memory versus take a 70% (=0.7x) performance penalty (in the very, very worst case).

Just for a sake of completeness: I did these numbers on my non AES-NI CPU, in a single thread, using the native Java Crypto library, which is faster than my own AES implementation. The worse your AES implementation is, the lower the relative performance hit. The better your SHA implementation is, the lower the relative performance hit.

Conclusion:
Advertising the HOdl algorithm as ASIC proof is total bullshit... the performance penalty when calculating cache entrys on-the-fly opposed to storing them in the 1GB lookup table makes every ASIC builder and their grandmother laugh...

What I don't understand/what I would appreciate if some one would answer:
Where does the algorithm origin from? I don't mean stuff like "it is similiar to Cryptonight" or something like that, but who made this algo? Also there seems to be zero documentation about the algo except for the code itself, which is a bad thing.

All things are not lost, I guess... from what I understand one could make an update to the algorithm via an update? I would strongly suggest it, since as of now, the algo doesn't hold up what it promises imho.
Again: I am _not_ a crypto expert or mathematician. I am simply your average Joe software engineer. And when I see a problem like this... everyone taking a closer look will...

EDIT:
@FreeTrade: I just re-read your post: "if you can calculate faster than you can retrieve from memory, that'll be optimal, but I doubt it" - that is totally besides the point! It is not about what is faster! It is about what are the time/space requirements for the algorithm! Even if not using the lookup table is 0.7x slower, it requires 250000x less memory! This is a great trade off and makes ASICs possible, which still operate on an algorithm, which is 0.7x slower, but do so 1000x faster (=700x total - of course this is not an accurate number again, but you hopefully get the point)!

I hope this is the right place to post this:

So I spend the last couple of days to program my first ever miner, which happens to be a HoDL Coin GPU miner... with not so great results. Here my findings so far:
- I am running a Core i3-3200 CPU without AES-NI. This gives me ~7 hash/s on the non-aes hodlminer per CPU thread(w0lf and optiminer keep crashing for me and I doubt they would improve performance as they mainly improve via AES-NI integration from what I understand)
- I started out implementing the hodlcoin algo on CPU and my implementation gave me ~3-4 hash/s per CPU thread
- I ported everything incl. a custom AES implementation to OpenCL (actually I didn't put the SHA stuff on GPU, but it is way less relevant than AES... for every sha execution there are at least 15 more AES executions)
- So my miner gives me now ~60 hash/s on an an rather old HD7850. It's 10-20x faster than the equivalent (unoptimized) CPU implementation. If I optimize the implementation, get something like a RX580 I'd guestimate a further 10x as the room for improvment, resulting in ~600 hash/s.
- and just to make it clear: the implementation _does_ work. I successfully submitted completed work to hodlcoin pool, which got accepted.

Conclusion so far: The GPU implementation as-is is good for people without AES-NI... on the other hand: you can get AES-NI nowadays for less than 50 USD. It may be possible to optimize the miner further, which would maybe even place it above an i7, but the improvement  would still be less than 50% in a rather good scenario. So a GPU miner may be feasable, but don't expect quantum leaps.

Another finding: The "1 GB space requirement" is complete nonsense. Give me 5kb memory and I give you an ASIC...

@achow101: Thanks for clarifying... I think I looked at too many bits yesterday. This helps a lot!

@DannyHamilton: Thanks as well for putting in the effort to color it and everything. However you did fake your comment a little bit:
You wrote:
I wrote:
See the additional zero there? That kind of bothers me still... Another implementation contains the zeros as well, so I think there is a problem with my Java implementation... I'll investigate...

EDIT: Simple problem... my Java code was swallowing leading zeros...
Bad code:
Good code:

Thanks again to all here for helping me with this problem!

EDIT2: So just for completness sake in case someone googles this... this Java function seems to produce the same thing as Bitcoin's Hash(...) function:

Thanks for your reply, I still don't understand the problem though. The array consists of 80 bytes all being of value 0x00. This should be the same regardless of byte order, shouldn't it?

EDIT: I don't know really why, but I tested the byte order just to be sure... as expected it doesn't make a difference for the byte array in question.

Hi, I am new here, so if this is the wrong forum, please let me know where this post is better placed.

I was trying to write my own miner, but simply don't understand what the Hash() function in hash.h is doing.
This is my code:

However when I try to do this with _any_ other SHA256 implementation I always get a different result (I tried three, which gave me the same result). Here is my Java code:

I thought maybe I have to double hash, but this leaves me with this:

So the hash I get from the Bitcoin implementation differs from any other SHA256 implementation for some reason... what am I missing? Am I using the algorithm wrong? Is it initialized differently (other implementation don't give me a possibility to parametrize the function)? Does it simply work differently (not according to the standard)?

Any help would be appreciated