4 ms·

Looking at the C code, here are a few suggestions: - __builtin_popcount() and __builtin_popcountll() are great gcc builtins which perform bit population counts

Looking at the C code, here are a few suggestions: - __builtin_popcount() and __builtin_popcountll() are great gcc builtins which perform bit population counts, useful for hamming distances (after the XOR operation, of course). [1] - avoid scanf(), which is costly. My approach was to generate a header file with the char * words[] array, and also a int words_len[] with, you guessed it, the pre-computed lengths. Then go for the memcpy() route and you're in a much better position. - speaking of memcpy, gcc provides one that should be optimal in most cases, but for really short words, it might be easiest to write your own. I came across a good article on it [2] but this is what I ended up using: void c_memcpy (char * dst, char * src, size_t len) { __builtin_prefetch(dst, 1, 3); while (len--) { *dst++ = *src++; } } [1] http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Other-Builtins.html http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Other-Builtins.h... [2] http://www.embedded.com/columns/technicalinsights/19205567 http://www.embedded.com/columns/technicalinsights/19205567

wooby 17y ago
Thanks for the tips. gcc builtins are definitely the next level for me. I'm curious about your scanf point though. I'm using scanf/strdup before the check loop to load the words into memory. Are subsequent memcpy calls on an implicitly loaded *char dict[] array faster on non-malloc'd memory for some reason?
- jcsalterego 17y ago
  Unfortunately, I have no empirical data or to support that hard-coding in a payload has an advantage over a dynamic allocation. As an aside, the Python dictionary (hash table for you rubyists/perlfaces) works this way, as it over-resizes to allow growth, unless you specify its maximum size (__slots__ I think?) My hope and understanding are that the compiler's static analysis skills will best align the given data, whereas something like malloc() would try to allocate on the heap as best it can with the open possibility of other data needing to be on the heap as well. The point I was driving at, and what I tried to do, was to hard-code in as many known variables as possible such that the compiler could do its thing and try to be as efficient as it could with the given data. This includes the word list, the list of lengths, the target hash -- none of which has to be done by hand, but rather a higher-level script called before compilation. Good times.
  - wooby 17y ago
    That makes sense, I might test it sometime.

wooby 17y ago

Thanks for the tips. gcc builtins are definitely the next level for me. I'm curious about your scanf point though. I'm using scanf/strdup before the check loop to load the words into memory. Are subsequent memcpy calls on an implicitly loaded *char dict[] array faster on non-malloc'd memory for some reason?

jcsalterego 17y ago
Unfortunately, I have no empirical data or to support that hard-coding in a payload has an advantage over a dynamic allocation. As an aside, the Python dictionary (hash table for you rubyists/perlfaces) works this way, as it over-resizes to allow growth, unless you specify its maximum size (__slots__ I think?) My hope and understanding are that the compiler's static analysis skills will best align the given data, whereas something like malloc() would try to allocate on the heap as best it can with the open possibility of other data needing to be on the heap as well. The point I was driving at, and what I tried to do, was to hard-code in as many known variables as possible such that the compiler could do its thing and try to be as efficient as it could with the given data. This includes the word list, the list of lengths, the target hash -- none of which has to be done by hand, but rather a higher-level script called before compilation. Good times.
- wooby 17y ago
  That makes sense, I might test it sometime.