## hashline32

## What is the collision probability of this hashing method?

The collision probability for this hashing method primarily depends on the bit-width of the return value and the number of hashed lines.

Although djb2 was initially designed as a 32-bit non-cryptographic hash, the local function djb2_64 actually implements a 64-bit variant of the djb2 algorithm. This is because it returns an unsigned long long (64-bit) and the bit shifting takes place within a 64-bit space.

Therefore, the output is also a 64-bit value in hexadecimal notation.

And yes, computing and outputting this as a 64-bit value also works on a 32-bit system when the code is compiled there. That is why this tool is named hashline32—it can be used on legacy systems without any issues due to backward compatibility.

## Collision Probabilities

| Number of Lines | Collision Probability | Risk |
|---|---|---|
| 1 Million | 1:37,000,000 | Extremely Low |
| 10 Million | 1:370,000 | Very Low |
| 100 Million | 0.027% | Noticeable and too high for critical systems |
| 5 Billion | 50% | Collision limit (50% chance) |
| 50 Billion | 99.99% | Almost guaranteed collision |

## Important Quirks of the Code

   1. Effective Bit-Width (64-bit instead of 32-bit): The code uses uint64 for the hash. The classic djb2 multiplier (33) is implemented via (hash << 5) + hash. Since no truncation to 32-bit occurs, you utilize the full 64-bit search space. Compared to a true 32-bit hash (where a 50% chance of collision is reached at around 77,000 lines), this massively increases security against accidental collisions.
   2. Non-Cryptographic Hash: djb2 is extremely fast but not resistant to malicious attacks (pre-image / collision attacks). If attackers control the input data, they can deliberately generate different lines that yield the exact same hash value within milliseconds (hash flooding).
   3. Input Dependency: Because djb2 relies heavily on byte values, it can sometimes lean toward patterns when dealing with highly similar, sequential strings (e.g., subtle nuances in URLs or log timestamps). This can slightly degrade the real-world collision rate compared to ideal mathematical theory.


## djb2 is and remains a non-cryptographic hash!!

This is crucial to understand:

 echo -n USER_000002 | hashline
 c029b2d299939045 USER_000002

 echo -n USER_000001 | hashline
 c029b2d299939044 USER_000001

 echo -n USER_000000 | hashline
 c029b2d299939043 USER_000000

Similar lines result in similar hashes.

Because this form of implementation lacks XOR, we do not have an avalanche effect!

## Tool Behavior

If a single line is larger than BUFSIZE (64 KB), the program does not crash, nor does a buffer overflow occur. Instead, it outputs exactly the maximum 64k (65,535 bytes) and then terminates cleanly with exit code 0.
Why? Anything else would mean undefined behavior. In the spirit of djb, a program must terminate if it would otherwise encounter undefined behavior. That is exactly what hashline does. When exceeding 64k per line, it does not simply split the data into two parts without asking, it sets no markers, and it does not silently manipulate the lines. It does not wait endlessly for a newline to generate a hash. It also does not allocate arbitrary additional memory only to eventually get killed by an external OOM killer if it never finds a newline. It uses the known, hard-coded, compiled-in, and detectable limit of BUFSIZE and terminates if the limit is exceeded.
From a data-logic perspective, terminating the program immediately is the only correct and safe way (Fail-Fast).
This behavior is a consistent and logical design decision. Since we define that lines over 64 KB (65,535 bytes)—just like an EOF—mark the end of the data stream, this behavior is by definition not a software bug, but a regular termination of the stream.
All possible alternatives would otherwise suffer from this practical issue:

* Discarding lines and continuing the search: If an attacker or a faulty system sends terabytes of data without a single \n, the program would read in circles indefinitely, calculate hashes for garbage, and waste CPU cycles without ever delivering meaningful data.

## Why does it terminate with exit code 0 (success) instead of exit code 1 or higher in this case?

Since the 64 KB limit per individual line is a known, fixed characteristic of the program, the behavior is deterministic for the user and thus perfectly documented. Furthermore, a separate exit code is not set because this is not an error state. The termination state can be recognized afterward even without evaluating the exit code by looking at the content itself—specifically, that the line length after the hash of the last hashline matches the defined limit. This is important when this data flows into log files, as logs usually do not log exit codes themselves. Therefore, the behavior is not logged and signaled via exit codes here, but is visible by the length of the content.
Due to the well-defined BUFSIZE limit, the program behaves like a secure filter that safely freezes processing if the specification is exceeded, flushes the current buffer, and terminates in a controlled manner. Combined with -fstack-protector-strong and -static-pie, this makes it a robust tool for its intended purpose.

## How do I prevent an attacker from using the 64k limit to crash my pipeline?

Prepend a | cut -c-65532 | in your pipe to cut off overly long lines beforehand. This way, hashline will not terminate because you never reach the limit. Additionally, you limit the resources available to your attacker.
This is not built into hashline because it is not the job of hashline and goes against the Unix philosophy. You should be able to decide for yourself how to handle this in your pipe.

## What if I have lines that are exactly 64k in size?

Yes. And the newline is +1 byte. What is the question?

## But what if I have lines larger than 64k and want to keep processing? What now?

In that case, you must prepend something like fold -w 65532 in the pipeline to actively force line breaks beforehand. This ensures hashline deliberately does not terminate and stays below the limit for the hash calculation. As a user, you are then consciously ordering this data modification and must account for it further down the line. You can also mark the end of the line with a flag of your choice to reverse the lines later. This is not the job of hashline. The hash will always only be calculated over byte sequences below the limit.
This is what modular and Unix-compliant software development looks like. According to the Unix philosophy ("Do one thing and do it well"), hashline does not have to solve the problems of incomplete or overly long lines.
As mentioned, the tool firmly assumes that a valid line fits into the 64 KB buffer. If the underlying data falls outside this norm, it is the pipeline's job to prepare the data.
An upstream command like:

... | awk '{while(length($0)>65535){printf "%s\036\n",substr($0,1,65532);$0=substr($0,65533)}print}' | ...

breaks the lines cleanly including a marker before they reach hashline. If you need this, you can use it in the chain, get a hash over the substring including the marker, and reverse everything later.

## Why do you do it this way?

This allows the code to follow the Unix philosophy while remaining highly performant for all other users, as it requires no complex, dynamic memory management (like realloc). It also stays secure, because the buffer remains static, completely eliminating the risk of heap exploits.
Please let me know if you would like to adjust any specific technical terms (such as formatting formatting preferences) or if you need help translating the command-line examples further!