9
\$\begingroup\$

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"));
\$\endgroup\$
7
  • 2
    \$\begingroup\$ Please add some description of your hashing algorithm. You will loose a lot of potential reviewers if they have to infer that knowledge from the code. Also please edit the title to not ask for improvements because that applies basically to every question on this site. Just state what your code does. \$\endgroup\$ – slepic Feb 11 '20 at 21:50
  • \$\begingroup\$ Thanks for the advice. I've edited the post. \$\endgroup\$ – thzoid Feb 11 '20 at 22:00
  • \$\begingroup\$ Is it possible for you to add some test code to demonstrate how the function is used? It would also help if the definition of HASH_LENGTH was shown. \$\endgroup\$ – pacmaninbw Feb 11 '20 at 22:04
  • \$\begingroup\$ Edited it! Thanks for the patience! \$\endgroup\$ – thzoid Feb 11 '20 at 22:11
  • 4
    \$\begingroup\$ What is the purpose of this hash function? Is it for data structures like a hash map? Is it for cryptography? Is it for something else? \$\endgroup\$ – Josiah Feb 11 '20 at 22:29
11
\$\begingroup\$

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.
\$\endgroup\$
4
  • 1
    \$\begingroup\$ I kinda tried to do everything from scratch, without many external libraries, just for studying. Thanks a lot for the helpful review. Now about your concerns, the "longer than HASH_LENGTH" was actually a bug I didn't notice. The inner loop is supposed to do inputLen iterations. Thanks for pointing that out. About the alphabet, what would you suggest to solve this problem? And do you have any suggestions on the XOR thing? Would mixing other operations in be of any help? Thanks again. \$\endgroup\$ – thzoid Feb 11 '20 at 23:40
  • \$\begingroup\$ Yes, mixing in other operations would help. \$\endgroup\$ – Josiah Feb 12 '20 at 8:07
  • \$\begingroup\$ As for the alphabet thing, the standard option is to separate out the hash calculation (which should be a nice even spread across all bits) from the conversion to something visible for debugging. When you do the visible thing, standard is to use something like Hex that can represent all the bits of the hash. But when you use the hash internally, you keep it raw. \$\endgroup\$ – Josiah Feb 12 '20 at 8:21
  • 1
    \$\begingroup\$ If you're wondering which operations to mix in, it's worth noting that "Add-Rotate-Xor" is a common design for hash functions. \$\endgroup\$ – James_pic Feb 12 '20 at 11:27
10
\$\begingroup\$

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?

\$\endgroup\$
6
  • \$\begingroup\$ I read somewhere that casting malloc()s to pointer types was a good practice, I'm not sure why, though. Thanks a lot for the helpful review. Just one question: why did you say I was reimplementing memset() less efficiently? How'd you reimplement it in a better way? \$\endgroup\$ – thzoid Feb 11 '20 at 23:36
  • 1
    \$\begingroup\$ You don't reimplement memset() - trust your compiler to have much better knowledge of the target architecture than we C programmers ever can. Each compiler can provide an implementation carefully targeted at its platform; portable code will not (and should not) do that. \$\endgroup\$ – Toby Speight Feb 11 '20 at 23:39
  • \$\begingroup\$ But doesn't memset() belong to <string.h>? Do these libraries vary from compiler to compiler? I thought they were components of the language itself. \$\endgroup\$ – thzoid Feb 11 '20 at 23:43
  • 1
    \$\begingroup\$ Yes, <string.h> is part of the Standard Library, and therefore supplied as part of your compiler. That means that it's provided as part of your development platform, and implementations do indeed vary. In particular, compilers are allowed to recognise Standard Library functions and handle them specially - for instance, see the Stack Overflow question, Can printf get replaced by puts automatically in a C program? \$\endgroup\$ – Toby Speight Feb 12 '20 at 7:20
  • \$\begingroup\$ Minor: "This is exactly what strlen() (in <string.h>) is for: int const inputLen = strlen(input);" --> except strlen() returns size_t. OP's code should be adjusted for that. \$\endgroup\$ – chux - Reinstate Monica Feb 12 '20 at 15:05
3
\$\begingroup\$

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);

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.