Simple hashing algorithm

Question

TL;DR: The algorithm receives a string as input, allocate another string to be the final digest, and start working on them. For each char on the digest (a null character on a first moment), it XORs it with every character from the original string, also XORing it with a set of "random bytes" that are specified in the beginning of the code.

Here are some results:

"000" = qpktluvsqpktluvs; "001" = bcygoiwnccxfohxn;

"abc" = ayedeufryzdfftds; "cba" = cqgleoxlarrnfnvm;

"aaaaa" = hingixcphingixcp; "aabaa" = aprndovlapgneovk;

Am I mathematically getting the full potential of the performance I'm using? How good would you say it is compared to other hashing algorithms? Thanks a lot for reading! This is my first hashing algorithm. My goal is to be simple and performatic. How can I improve it?

#define HASH_LENGTH 16
char *hash(char *input){
    // Alphabet and length
    const char alphabet[] = "abcdefghijklmnopqrstuvwxyz";
    const int alphabetLen = sizeof(alphabet)/sizeof(char) - 1;

    // Randomization variables and length
    const char vars[] = {
        0xA6,
        0xC1,
        0x5E,
        0x31,
        0xF5,
        0x88,
        0xA1,
        0xE2
    };
    const int varsLen = sizeof(vars)/sizeof(char);

    // Digest (where the hash is made)
    char *digest = (char*)malloc(sizeof(char) * (HASH_LENGTH + 1));

    // Input length calculation
    int inputLen = 0;
    while(input[inputLen] != '\0') inputLen++;

    // Digest cleaning
    int i;
    for(i = 0; i < HASH_LENGTH; i++){
        digest[i] = 0;  
    }

    // Hashing process
    int j;
    for(i = 0; i < HASH_LENGTH; i++){
        // XORs digest[i] with vars[input[j]]
        for(j = 0; j < HASH_LENGTH; j++){
            digest[i] ^= vars[input[j % inputLen] % varsLen];
        }
        // XORs digest[i] with input[i] + vars[i]
        digest[i] ^= input[i % inputLen] + vars[i % varsLen];
    }

    // Translates digest to desired alphabet
    for(i = 0; i < HASH_LENGTH; i++){
        j = digest[i] > 0 ? 1 : -1;
        digest[i] = alphabet[digest[i] * j % alphabetLen];
    }
    // Finalizes digest string
    *(digest + HASH_LENGTH) = '\0';

    return digest;
}

This is how the function is called:

printf("%s", hash("foo"));

Answer 1

I'm not particularly familiar with C, but I have a few observations that may be helpful.

I like the attention to zeroing out your digest before you start. Using uninitialised memory is the sort of bug that can go unnoticed for a while, and it's good that you've caught it.

At the same time, I'm slightly alarmed that you're doing everything with raw loops, instead of using standard library functionality that does the same job. For example your loop to find inputLen could be replaced by a call to something like strlen and your loop to zero the array with a call to memset. As well as generally being more confident that you're using a tested and optimised routine, using library functions makes it easier to read and reason about your code.

I also quite like your use of comments. They're well placed, complementing the code and explaining some of the whys where the code explains the hows.

---

As for the hashing itself, I'm sure that the output looks fairly random, but it's actually doing a lot of work for the level of hashing that it supplies.

My top concerns:

1. If the input is longer than HASH_LENGTH, the latter part of the input is completely ignored.
2. XOR is a standard building block for this sort of low level stuff, but one of the key properties of XOR is that it undoes its own work. That is to say, because your for loop with j is only doing XOR it will confuse rather less than you'd expect for the work that goes into a nested loop.
3. The space allocated to digest at the end is underused. For example, because it's restricted to that alphabet, the first three bits of every byte will be "011". That has implications for use with, say, hash maps because the hash map will allocate 87.5% of its slots to values this hash function can never fill for any possible input.

Answer 2

We really need to start by defining the kind of hash function we've created - this doesn't appear to be a useful cryptographic (one-way) hash function, yet creating strings as output seems to be a poor choice for hashes used for performance purposes (as keys in unordered maps and sets, for example). What is the intended problem domain here?

We have a very low density of outputs. On a system with 8-bit char, we use only .000000000000013% (significantly less than one quadrillionth) of the available 16-byte results. That's very inefficient use of storage.

---

Should the function be allowed to modify the contents of input? If not, then it should be declared as char const*.

---

Since we return a pointer to allocated memory, the documentation needs to be much more clear that it's the caller's responsibility to call free() when it's no longer required.

---

alphabet and vars can be shared across all invocations, so should be declared static.

---

All these values are potentially out of range of char, as CHAR_MAX may be as low as 127:

const char vars[] = {
    0xA6,
    0xC1,
    0x5E,
    0x31,
    0xF5,
    0x88,
    0xA1,
    0xE2
};

Use a type with a guaranteed large enough range, such as int or unsigned char. How were these constants generated? It's worth a comment explaining how these improve the algorithm, because it's not obvious to a casual reader.

---

If we declare malloc() before we use it, we won't need to cast its result:

#include <stdlib.h>

char *digest = malloc(HASH_LENGTH + 1));

Note that sizeof (char) cannot be other than 1, since sizeof works in units of char.

---

malloc() will return a null pointer when it fails - we mustn't dereference the result until we know it's a valid pointer.

---

// Input length calculation
int inputLen = 0;
while(input[inputLen] != '\0') inputLen++;

This is exactly what strlen() (in <string.h>) is for:

size_t const inputLen = strlen(input);

BTW, it's probably worth using size_t (or at least unsigned types) for HASH_LENGTH and varLen, too, and for the indexing iterators i and j.

---

int i;
for(i = 0; i < HASH_LENGTH; i++){
    digest[i] = 0;  
}

<string.h> also contains memset() - don't reimplement it yourself. Your compiler may be smart enough to spot the pattern and convert it to more efficient form (e.g. writing in units of your processor's word size), but even if it does, you've obscured what's happening here, and programmer time is much more expensive than CPU time.

---

The XOR loops don't seem to consider any of the input string after the first HASH_LENGTH characters. That means you'll get lots of collisions for strings sharing a common prefix.

The nested loops mean we're doing much more work than traditional hash functions, which examine each input character just once (and are O(n) in the length of input).

---

Hashing the empty string gives undefined behaviour, because inputLen is then zero, and % 0 is undefined. That's a serious bug.

---

digest[i] > 0

On systems where char is an unsigned type, this may be true much more often than on those where it's signed - that looks like a bug. Reading on, it appears that you're just using this to implement your own abs(); don't do that - include <math.h> instead.

---

    digest[i] = alphabet[digest[i] * j % alphabetLen];

That will give you a non-uniform distribution, unless you can somehow arrange for alphabetLen to be an exact factor of UCHAR_MAX.

---

*(digest + HASH_LENGTH)

That's a convoluted way to write digest[HASH_LENGTH] - why are you going to such lengths to make the code hard to read?

Answer 3

Review of OP's post and answer.

Bug

digest[i] ^= vars[input[j] % varsLen]; is undefined behavior, UB, when input[j] < 0.

Bug

hash("") attempts % 0 withdigest[i] ^= input[i % inputLen] + vars[i % varsLen];

Failure on long strings

strlen(input); can exceed INT_MAX. size_t const inputLen = strlen(input); size_t i, j; is better.

abs() not really needed

char *digest as unsigned char *digest would negate the need for abs() in abs(digest[i])

Fundamental issues as code uses char rather than unsigned char

Using unsigned char rather than char would improve hash quality and maybe speed over when char is signed.

char vars[] = { 0xA6, ... remains problematic as when char is signed, conversion of an out-of-range value to char is implementation defined and may not perform as desired. Simplify all this potential signed hashing with unsigned char. The return type can remain char *.

Note that the C library functions perform internally as if char was unsigned char even when char is signed.

Simplification

char *digest = malloc(HASH_LENGTH + 1); memset(digest, 0, HASH_LENGTH); ...digest[HASH_LENGTH] = '\0'; can be replaced with char *digest = calloc(HASH_LENGTH + 1, sizeof *digest);