cmuratori/meow_hash

Official version of the Meow hash, an extremely fast level 1 hash

meow_hash's Issues

Request: Windows build for meow_search app

Hi!

Is there any pre-built Windows binaries? Tried to build on my VS2015 and everything seems to be fine, but when I try to run meow_search D:\dir D:\1.txt I'm immediately getting app crash :(

If there is a working binary it would be very nice to download it.

Thanks!

Benchmark

from http://mollyrocket.com/meowhash:

It’s the fastest hash function we know of by a factor of at least 3.

ok that is great - but what are we comparing it against

would be nice to see what the competitors are and/or what the methodology was

thanks

Example program does not work on Windows

Hi,

I think it is worth adding a note on the example program stating that it does not work properly on Windows. I ended up wasting an embarrassing amount of time thinking it was working as everything seems fine in the output, except hashed files do not match hashes generated using other tools.

It seems the issue for Windows is that the following will not reliably produce the correct size of the file:

fseek(File, 0, SEEK_END);
Result.Size = ftell(File);
fseek(File, 0, SEEK_SET);

Errors in contributors links

The links for RAD game tools and Martins Mozeiko sites contain typos.

RAD game tools site doesn't work with https, only http. Should be http://radgametools.com
Martins is spelled wrong, should be https://martins.ninja/

Most probable collision

I have looked a bit at the probability for random collisions, an important measure in this regard is how little data one can change to produce almost-identical files with the same hash-value.

My best bid so far is that after changing one almost arbitrary byte to any different value, one need to only change 4 consecutive bytes in the following data-block of the same sub-stream (i.e. approximately 256 bytes ahead) to get back to the original hash. This is because one AES round doesn't fully mix the state.

Here is a miniature example of how such a collision works on the internal state, for the real hash algorithm the changes would need to be further apart, but otherwise similar:

#include <stdio.h>
#include "meow_intrinsics.h"

static void
PrintHash(meow_u128 Hash)
{
	meow_u32 *HashU32 = (meow_u32 *)&Hash;
	printf("    %08X-%08X-%08X-%08X\n",
		HashU32[3],
		HashU32[2],
		HashU32[1],
		HashU32[0]);
}

int main()
{
	meow_aes_128 S0 = Meow128_ZeroState();
	char* input = "A little string of some nice test data to test on.";
	meow_aes_128 S1 = Meow128_AESDEC_Mem(S0, input);
	meow_aes_128 S2 = Meow128_AESDEC_Mem(S1, input + 16);
	char* input2 = "A lIttle string of some niceE%\x1a\x35t data to test on.";
	meow_aes_128 S1a = Meow128_AESDEC_Mem(S0, input2);
	meow_aes_128 S2a = Meow128_AESDEC_Mem(S1a, input2 + 16);
	PrintHash(S2);
	PrintHash(S2a);
	getchar();
	return 0;
}

Is this actually a problem for a non-cryptographic hash function? In most cases probably no, while the collision strength is only 32 bits for a change in the right pattern, I expect that pattern of change to be rare. Best scenario I can think of is a 32-bit colour 64 pixels wide bitmap file, where the pattern might emerge by changing two vertically adjacent pixels.

The cheapest fix I can think of is running the AES function twice with the same "key" on every second input round, since this collision relies on exact control of two consecutive blocks, disturbing it in one of those blocks is enough. No guarantee that that doesn't leave any other weakness intact, but I so far don't see it.

v0.5 - Should we take a nonce?

We are "already ingesting" a nonce, but we currently just fill it with zeroes. There's room for 128 bits + 64 bits, so one 16-byte nonce and one 8-byte nonce.

My initial thought was perhaps the main routine doesn't bother, but the incremental code could support an additional "SetNonce(u64, u128)" or something?

- Casey

Inlining Failed

I could just be compiling incorrectly, but I'm importing meow_hash_x64_aesni.h into my project. then running: g++ -o program program.cpp

I get this error:

In file included from /usr/lib/gcc/x86_64-linux-gnu/7/include/x86intrin.h:45:0,
                 from meow_hash_x64_aesni.h:131,
                 from program.cpp:49:
/usr/lib/gcc/x86_64-linux-gnu/7/include/wmmintrin.h:44:1: error: inlining failed in call to always_inline ‘__m128i _mm_aesdec_si128(__m128i, __m128i)’: target specific option mismatch
 _mm_aesdec_si128 (__m128i __X, __m128i __Y)
 ^~~~~~~~~~~~~~~~
In file included from program.cpp:49:0:
meow_hash_x64_aesni.h:173:25: note: called from here
 #define aesdec(A, B)  A = _mm_aesdec_si128(A, B)
                         ^
meow_hash_x64_aesni.h:198:1: note: in expansion of macro ‘aesdec’
 aesdec(r4, r2); \
 ^~~~~~
meow_hash_x64_aesni.h:429:5: note: in expansion of macro ‘MEOW_SHUFFLE’
     MEOW_SHUFFLE(xmm3, xmm4, xmm5, xmm7, xmm0, xmm1);
     ^~~~~~~~~~~~

Would appreciate any help. Than kyou.

How deterministic is Meow hash?

I have tests that randomly fail because I also test the output hash string. I have witness the output fluctuate between at least 2 variants given the same input.

Make input parameters const?

Input pointer parameters in the function signatures are not const, e.g.:

static meow_u128 MeowHash(void *Seed128Init, meow_umm Len, void *SourceInit)

This gives the impression to readers on a glance that the functions are actually modifying the data they are hashing, which I'm fairly sure is not the case!

It also has the inconvenience that to hash an object that is already const qualified you have to add an explicit cast, e.g.:

uint64_t HashBlob(const Blob* pBlob)
{
    result = MeowHash(MySeed, sizeof(Blob), (void*)pBlob);
    ...
}

Could we please have the function signatures updated to take all input parameters by const pointer?
Thanks!

More testing of prefetching

Probably need a wider array of test machines to see how to make this optimal.

- Casey

v0.5 - Check meow_u16/32 to see if they can be removed

They may no longer be necessary defines.

- Casey

v0.5 - MSVC doesn't compile the loop properly

CLANG gets the full speed, MSVC doesn't - I haven't looked into it yet but this is a reminder to see if MSVC can be coerced into not screwing it up.

- Casey

Profiling via meow_bench on Linux doesn't seem to work

I am not familiar with Linux OS peculiarities, but I cannot seem to get real performance measurements using rdtsc() on Linux :(

I have two effectively identical machines, one with Windows, and one with Linux. Running meow_bench on both yields "correct" results on Windows where the bytes/cycle drops off after the input buffer gets sufficiently large to be out-of-cache. However, on Linux, this never happens. You can run 8GB through it, and it still thinks it's getting 16 bytes/cycle. This shouldn't be possible!!

I've tried to turn off turboboost, turn off power throttling, turn off this, turn off that, but I cannot seem to get it to change. Does anyone have any pointers? I'd like to know what's going on here.

- Casey

segfault on unaligned input

It seems there is a requirement for inputs to be aligned to 8-byte boundaries.
I'm seeing seg-faults per the below when that isn't the case (though somewhat inconsistently).

Is that an accurate statement, or have I messed something up? :)

`Process 29306 stopped

• thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=EXC_I386_GPFLT)
  frame #0: 0x00000001060b6832 meow_hash.soMeowHash1(unsigned long long, unsigned long long, void*) + 450 meow_hash.soMeowHash1:
  -> 0x1060b6832 <+450>: movdqa (%rax), %xmm1
  0x1060b6836 <+454>: movdqa %xmm0, -0x7a0(%rbp)
  0x1060b683e <+462>: movdqa %xmm1, -0x7b0(%rbp)
  0x1060b6846 <+470>: movdqa -0x7a0(%rbp), %xmm0
  Target 0: (postgres) stopped.
  (lldb) bt
• thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=EXC_I386_GPFLT)
  • frame #0: 0x00000001060b6832 meow_hash.soMeowHash1(unsigned long long, unsigned long long, void*) + 450 frame #1: 0x00000001060b7fef meow_hash.someow_text + 479`

Consider using -mavx rather than -mavx2 in build.sh's build of meow_bench

-mavx -maes is fine on both Linux/clang++ and Linux/gcc++.
-mavx2 doesn't seem to actually emit avx2-specific code on clang8, or meow_bench is getting lucky. :)
But -mavx2 prompts GCC to emit code that genuinely needs avx2 (and will crash on avx1-only), which seems surplus to the requirements of the actual meowhash implementation.

.NET Core 3.1 port.

Not really an issue, but in this gist is a port of the algorithm to C# using the new .NET Core intrinsics.
Feel free to include this in repro or I can make a separate repo for it and post/maintain it on nuget.
whatever you feel is appropriate.

https://gist.github.com/tvandijck/a9160c49a36ba652e0cab647cbc1a1b8

v0.5 - 32-bit compatible version of MeowU64From

Right now it only works in 64-bit mode.

- Casey

v0.5 - build.sh should be updated to the new directory structure, etc.

I believe the Linux build should be mostly working, so we just need to update build.sh to use the new directory structure, and then I think we're good.

- Casey

File comparison example code

I have learned from the false collision reports is that people may make mistakes when testing for collisions :) So I think what probably needs to happen to reduce this problem is that the Meow hash distribution should come with a Windows / Linux example program that tests all the files in a directory structure of your choice, and reports the collisions. That way people don't have to write it themselves, and won't make mistakes and think they have collisions when they don't.

- Casey

A Sun port i did on a whim, using the system compiler...

bench32_sun.txt
bench64_sun.txt

Some benchmarks taken on the lone system I own that has AES and AVX in the FPA.

Used the default system compiler (Sun C++ v5.15 of ProWorks 12.6) for this, and have some local patches in my own repo. Probably of very little general interest, just wanted to post some recent stats.

Benchmark Results From Ryzen 7 1700 1st Gen

This is not an issue as such, but Casey mentioned on the HH stream the other day about testing Meow hash on AMD zen architecture.

Although i can't send you my machine, I do own a 1st gen Ryzen 7 1700 https://en.wikichip.org/wiki/amd/ryzen_7/1700
So i've compiled and run the benchmarks using msvc 2017, and run the bench marks (windows 10),

Interesting to see the dropoff in speed at 8Mb, which matches with the 2x8mb of cache in the processor (i assume 8Mb per 4 core cluster), and at 32Kb (which is the L1 data cache size).

[results_ryzen7_1700_1stgen.zip](https://git

hub.com/cmuratori/meow_hash/files/3437634/results_ryzen7_1700_1stgen.zip)

Possible to operate on an input stream rather than a fixed size buffer?

This is pretty great. I already have a use case for this that I'd like to explore.

How would the algorithm lend itself to operating on an input stream, where the total buffer size may not be known up front?

Would it be possible to split the input source into fixed-size chunks and then combine the resulting hashes in some way that would yield correct results?

meow_bench probably needs a rewrite at this point

It's kind of a pile.

I'm not really sure exactly how this kind of speed testing should be done. It's really pretty dicey to get good measurements. This is not a specific issue, just a reminder that we should make a better meow_bench.

- Casey

v0.5 - mmap/mprotect page guarding for meow_test on Linux

Right now meow_test doesn't actually make a guard page on Linux, only on Windows.

- Casey

MeowU64From only returns the first 64 bytes of the hash

When trying to get the result of a computed hash using MeowU64From, only the first 64 bytes are returned, regardless of the value of the second function argument.

Here's a simple c/c++ program I wrote to demonstrate the issue:

#include <iostream>
#include "meowHash.h" //the header file that contains the Meow Hash source code

void main(){
	
	//fill buffer with data.
	
	int bufferSize = 50;
	
	char* buffer = (char*)malloc(bufferSize);
	
	for(int i = 0; i < bufferSize; i++){
		
		buffer[i] = i;
		
	}
	
	//hash and print.
	
	meow_u128 hash = MeowHash(MeowDefaultSeed,bufferSize,buffer);
	
	long long unsigned hash1 = MeowU64From(hash,0);
	long long unsigned hash2 = MeowU64From(hash,1);
	
	std::cout << std::hex << hash1 << " " << hash2 << std::dec << std::endl;
	
	long unsigned hash3 = MeowU32From(hash,0);
	long unsigned hash4 = MeowU32From(hash,1);
	long unsigned hash5 = MeowU32From(hash,2);
	long unsigned hash6 = MeowU32From(hash,3);
	
	std::cout << std::hex << hash3 << " " << hash4 << " " << hash5 << " " << hash6 << std::dec << std::endl;
	
}

When run, it produces this output:

f977fc4881456a98 f977fc4881456a98
81456a98 f977fc48 d3d8ef6a 4e7a8b47

The U32 parts can be accessed fine, but trying to access the hash as a pair of U64 parts does not work, as it instead only returns the first 64 bytes.

Compiler: Microsoft Visual Studio Community 2019 16.4.5 using Visual C++ 2019
CPU: Intel Core i5-9300H CPU
OS: 64 bit Windows 10

Modern C++ rewrite

Hello, just wanted to showcase my rewrite of the meow hash algorithm, using modern C++ features to tidy up the codebase and get rid of the several instances of undefined behavior I found.

https://github.com/RedSpah/meow_hash_cpp

I didn't make any changes that would obviously slow the execution speed down, but note that I haven't benchmarked my version yet, so I can't know for sure.

Buffer overflow when size is not a multiple of 16 (ASan).

I have observed this in MeowHash() but likely the other functions have the same problem. This can be reproduced by running this very simple example with Address Sanitizer enabled (you'll need Clang on linux/macOS):

#include <meow_hash/meow_hash_x64_aesni.h>

static char hashBuffer[128 + 3]; // any size where % 16 != 0

uint64_t Test_BufferOverflow()
{
    meow_u128 hash128 = MeowHash(MeowDefaultSeed, sizeof(hashBuffer), hashBuffer);
    return MeowU64From(hash128, 0);
}

int main()
{
    uint64_t h = Test_BufferOverflow();
    return (int)h;
}

The following error is flagged by ASan:

==78==ERROR: AddressSanitizer: global-buffer-overflow on address 0x0000500b8f6f at pc 0x000045990739 bp 0x0007ef343590 sp 0x0007ef343588
READ of size 16 at 0x0000500b8f6f thread T0

0x0000500b8f6f is located 12 bytes to the right of global variable 'hashBuffer' defined in 'main.cpp:27:13' (0x500b8ee0) of size 131
SUMMARY: AddressSanitizer: global-buffer-overflow (Test.elf+0x9cc739) at (Test.elf+0x9cc739)
Shadow bytes around the buggy address:
  0x01000a017190: f9 f9 f9 f9 00 00 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
  0x01000a0171a0: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 f9 f9 f9
  0x01000a0171b0: f9 f9 f9 f9 01 f9 f9 f9 f9 f9 f9 f9 00 00 f9 f9
  0x01000a0171c0: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 00 f9 f9
  0x01000a0171d0: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 00 00 00
=>0x01000a0171e0: 00 00 00 00 00 00 00 00 00 00 00 00 03[f9]f9 f9
  0x01000a0171f0: f9 f9 f9 f9 00 f9 f9 f9 f9 f9 f9 f9 00 00 00 00
  0x01000a017200: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x01000a017210: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x01000a017220: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x01000a017230: 00 00 00 00 00 00 00 00 00 00 00 00 f9 f9 f9 f9
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
This process has been stopped due to a fatal Address Sanitizer error.

The overflow happens specifically in the loop that handles the residual bytes that are not mod of 16.

v0.5 - Change header comments to indicate we're aiming for Level 3

Perhaps with the caveat that we need more crypto people looking at it before we really know how resilient it will be.

- Casey

v0.5 - Update the Meow Hash website once v0.5 is ready to pull

Just a reminder that I need to update Molly Rocket's page about Meow Hash once v0.5 is ready.

- Casey

LongNeighbors

@hmakholm has a smhasher test called LongNeighbors. This test creates similar strings by flipping bits and looking for collisions. I ran Meow 128 through this test and it fails that.

A description of this test is LongNeighborTest

My driver for Meow in the smhasher test is here smhasher, specifically, this MeowTest.cpp

I don't think there is a bug there, but maybe... I was able to modify the Meow algo to pass this test, but I don't think it would be acceptable: doubling the number of AES rounds. This causes the throughput to be 50% of the current version (smhasher reports 24MiB vs 48MiB unmodified).

It's easy to recreate this test under Linux:

$ git clone https://github.com/injinj/smhasher
$ cd smhasher
$ cmake src
$ make
$  ./SMHasher Meow128 -o                                                                                                   
-------------------------------------------------------------------------------
--- Testing Meow128 (Meow 128-bit)

[[[ Keyset 'TestLongNeighbors' Tests ]]]

Looking for 2-bit collisions in the last 2400 bits.
Looking for 4-bit collisions in the last 2048 bits.
Looking for 6-bit collisions in the last 160 bits.
Trying bases of length 10 to 300, 5 of each length.
......[16]...............[32].....
This horrible collision has surprise score 4.14258e+25 and length 38 bytes:
000: B3 C1 BA 57 71 18 B2 6B AE C8 3A C1 A9 04 C4 E3 3B F6 F0 62 84 1F 78 99
                                                          ^D2^     ^1B^
018: BD CF 10 8E 9A 73 32 4F 29 17 84 B8 86 33
    ^B5^                 ^4D^     ^8C^
The hashes are length 16 bytes:
000: B9 4B AF 11 1D DD 42 F0 15 78 BA CA 97 06 7E F8
....
This horrible collision has surprise score 4.37134e+25 and length 42 bytes:
000: 99 AD 12 8C FE E7 7D 2E 17 89 47 27 AC C6 75 95 FE CF 12 8C 95 8B 91 4D
                                                                      ^93^
018: 01 BC 85 56 D9 50 FE 6D A5 0F 89 77 E2 EF A5 B6 87 E7
       ^3C^     ^DB^                 ^F7^     ^85^     ^67^
The hashes are length 16 bytes:
000: 42 4A 96 AC 8A A1 E9 FF 44 12 80 C6 20 82 CD DA
.
This horrible collision has surprise score 4.61799e+25 and length 43 bytes:
000: 90 A5 12 8C BF E5 7F 2E 57 CB 05 27 E4 CE 35 95 F7 C7 12 8C D7 99 91 5D
018: 41 BE C7 54 D3 18 BE ED AC 47 8B 75 EB 37 07 A4 9C 64 B8
    ^C1^                 ^6F^                       ^DC^
The hashes are length 16 bytes:
000: 9B E8 1A 94 69 45 EB BC EF 73 19 4F C9 38 A6 10
...
This horrible collision has surprise score 6.49333e+25 and length 46 bytes:
000: BD 8D 12 8C FB EE 75 2E 17 80 4E 26 8C E7 75 94 DA EF 12 8C 95 CA 91 0D
018: 08 BD 8D 5F F2 78 FF 64 88 27 88 3F 8E 8F CE FC E2 8A 99 CE 2B E3
                ^D2^                 ^7F^              ^18^     ^0B^
The hashes are length 16 bytes:
000: 35 C1 E6 5B 6B 66 C7 28 52 CB 9D 10 E1 87 AD A6
..[48]...............[64].

Among 285 tested bases, we expected 2.30799e-25 bads. Actually there were 5.
*********FAIL*********

_ReadWriteBarrier() deprecated

FYI- Should probably replace its usage in MeowHash

https://docs.microsoft.com/en-us/cpp/intrinsics/readwritebarrier?view=vs-2019

New benchmarking is perhaps more accurate, but difficult to stabilize

With the v0.3 branch, I've tried to capture a lot more of the time spent in the hashes, including any pipelined computations, as well as the full cost of branches. I may have succeeded a little bit, but the cost is that the benchmarking is very hard to stabilize now. I would be interested in suggestions regarding how to get more consistent results, within reason (obviously there are entire systems designed for benchmark stabilization that are outside the scope of Meow hash).

- Casey

Is there any way to make compilers execute a proper rdtsc (or rdtscp)?

So, I would like to improve the accuracy of meow_bench, and among other things I am doing, I would like to try to get the rdtsc's to behave properly. In ASM, you can do some fanciness where you set up a dependency chain to force the rdtsc to happen more accurately, but I don't know if there's any modern compiler gyrations you can do to make CLANG or MSVC output something usable here. Anyone have any ideas? I don't think MSVC supports inline assembly anymore, but on CLANG maybe it would work to just use inline assembler...

- Casey

Full 128-bit collision between two files

Hello,

Your web page for Meow hash says to report collisions on GitHub. I have two PNG files that meow_search reports as colliding:

meow_search 0.5/calico results:
    Root: .
    Completed on: Sat Jun 26 08:38:34 2021
    Files: 2
    Total size: 19.00kb
    Duplicate files: 0
    Files changed during search: 0
    Access failures: 0
    Allocation failures: 0
    Read failures: 0
    [Meow128] Meow 128-bit AES-NI collisions: 1
        E936866F-6965CB25-D2F8F5AA-D04E8914:
            ./icon2.png
            ./icon1.png
    [Meow64] Meow 64-bit AES-NI collisions: 1
        00000000-00000000-D2F8F5AA-D04E8914:
            ./icon2.png
            ./icon1.png
    [Meow32] Meow 32-bit AES-NI collisions: 1
        00000000-00000000-00000000-D04E8914:
            ./icon2.png
            ./icon1.png

The files are here:

Thanks.

Trouble with the final mixdown

The current v0.3 branch's mixdown isn't good. The v0.1 mixdown is still the best for collision resistance, it seems. It would be nice if there was a more systematic way to analyze it. Passing smhasher really doesn't tell you much - a lot of things will pass smhasher but won't actually be collision resistant in practice.

I will probably roll back the mixdown to a v0.1 mixdown style for the official v0.3 commit, but afterward it would be nice if there was a more thoroughly analysis of exactly what has to happen with the mix.

- Casey

Unresolved issues from performance profiling

1. We do not know why CLANG generates subtract-from-pointer loads instead of add-to-pointer loads. It says it's faster when it generates the code inside meow_bench, but when we extract the ASM and run it ourselves under perf, vtune, or meow_bench itself, it is slower than add-to-pointer! This needs to be resolved, and what exactly CLANG is doing with meow_bench to get these results needs to be investigated.

2. We do not know why MSVC generates slower code on the loop than the hand-written ASM version, but it does appear to do so. I need to verify this by using the hand-written ASM that exactly replicates the MEOW_SHUFFLE part of the hash, which I had not done yet. But in general, we would like to be able to use perf counters to see what about MSVC's register allocation is causing the snafu.

3. We do not know why perf stat seems to be reporting lower numbers than we would expect. This may be due to excessive startup code or something else bad happening. We should try to stabilize the numbers so we can get 2.8 IPC, which is what we seem to observe on Windows, although there could be reasons why that would not be the case...

- Casey

256-bit variants

It would be great if MeowHash has a 25-bit variants for those who wants both accuracy and speed in a non-cryptographic setting (as fast or faster than FNV-1a)

Please post here if you can run Meow on a large dataset!

Hash tests are hard to come by, so testing Meow has been a mix of us testing our dataset for collisions and verifying that smhasher doesn't find anything suspicious. But that's not really sufficient. Anyone particularly interested in trying out Meow who has a large dataset test, please post here so I can coordinate with you as I try to finalize the finer points of the implementation. It would be very nice to be able to verify that we don't break anything with changes!

Thanks,
- Casey

PS. And I guess even if you don't have a large dataset, if you just have some useful hashing case that might find collisions we don't know about, that helps too!

Are there any other hashes we should be benchmarking against?

I used the ones I could find that were supposed to be speed-oriented. But I may have missed some.

- Casey

v0.5 - Import the correct types/defines from the old meow_intrinsics.h

Need to do a pass on the header to make sure we are still doing all the correct platform checking that was working out for v0.4.

- Casey

Meow "macroblock" mode

As of v0.2 there is a new "macroblock" mode that is experimental and supports multithreading. It is probably not what should be standardized, but it is a starting point. It was initially suggested by Jeff Roberts, and Fabian Giesen suggested possibly using a tree construction instead, for more distribution potential.

I'd be interested to hear thoughts on it. I'll take a look at it again in the future for v0.3.

- Casey

protected mode benchmark

and now, a benchmark of this algorithm, compiled for a i686 target machine in legacy protected mode

limiting factor is most likely the low-power mobile CPU (Pentium J3710) and the somewhat underpowered core memory (DDR3L-1600). this test was done with EIST turned OFF

this also happens to be the only device I own that has any kind of AES instructions in the i687, all others are Core2 or earlier

How much do you expect to change until version 1.0?

If you don't know the answer to this, no problem at all.

I'm maintaining a Golang version of Meow hash, and wondering whether I should take the effort to stay in sync, or hold off and wait for the dust to settle?

Use streaming construction to hash files

To allow for hashing files larger than available memory, and to prevent possible incompatibilities with ftell on 32-bit builds, I'd like to stop reading files into memory wholesale and start using a fixed-size buffer that gets repeatedly fread() and handed to Meow as a chunk.

- Casey

Should there be a C implementation?

C/C++ are terrible at dynamic fallbacks, since they can't JIT :( So it sucks to have to have lots of paths. But it's probably unavoidable. At some point there will have to be a straight C path, and if AES instructions aren't available, it can fall back.

- Casey

dotnet (c#) bindings

I'm interested in using meow hash in c#.
Does a binding exist for dot net?

meow_search does not work with MSVC

Because malloc(a) is defined as _aligned_malloc(4,a) in meow_test.h.

Thus any malloc will allocate only 4 bytes with alignment a. This means that either _aligned_malloc will crash program if a is not power of two, or memory corruption will happen when a > 4.

Not sure of the intention here, but should malloc be overridden at all? It is used only to allocate entry/file structures or path strings, not the file contents itself.

Also I think aligned_alloc in meow_test.h should be in #ifdef _WIN32 and not inside #ifdef _MSC_VER, because clang & gcc on Windows does not have aligned_alloc. They have _aligned_malloc though because they use MSVC runtime.

Build modifications for MacOS X?

As of the v0.2 update, meow_hash.h should build out-of-the-box on Windows MSVC and Linux CLANG. I would be interested to know what would be necessary to make build.sh/meow_hash.h work on MacOS X. For those with up-to-date MacOS X machines, have you tried building it? What changes are necessary to make it work?

Thanks,
- Casey

v0.5 - Add the "levels of hashing" document in here as a .md?

This one is all you @NoHatCoder :) Not sure what you have planned for that, but it seems like we should check in a copy of your blog post at some point when it is ready, just so people can understand what is going on here with hash levels. Maybe we make a "doc" directory? I can then link to it with the main readme.md (assuming GitHub actually has a way to do that... I will check).

- Casey

Should "Source" be "SourceInit" here?

meow_hash/meow_hash.h

Line 384 in 5ceaf14

MeowHash2(meow_u64 Seed, meow_u64 TotalLengthInBytes, void *Source)