Add POSIX CRC32 algorithm implementation to common library

Signed-off-by: Mel <mel@rnrd.eu>

1 files changed, 48 insertions, 0 deletions

diff --git a/boot/common.c b/boot/common.c
index e696663..388aea5 100644
--- a/boot/common.c
+++ b/boot/common.c
@@ -4,6 +4,8 @@
  * allocation done purely statically.
  */
 
+#include <stdarg.h>
+#include <stddef.h>
 #include <stdint.h>
 #include <stdio.h>
 #include <stdlib.h>
@@ -153,3 +155,49 @@ string_length(struct String s)
 {
     return s.length;
 }
+
+// single iteration of the CRC32 checksum algorithm
+// described in POSIX.
+// see: https://pubs.opengroup.org/onlinepubs/9799919799/utilities/cksum.html
+// used by `crc32_posix`.
+uint32
+crc32_posix_iteration(uint32 initial_hash, uint8 octet)
+{
+    const uint32 iso_polynomial = 0x4C11DB7;
+
+    octet ^= initial_hash >> 24;
+    uint32 hash = 0;
+    uint32 poly = iso_polynomial;
+    for (uint8 bit = 0; bit < 8; bit++) {
+        if (octet & (1 << bit)) hash ^= poly;
+
+        uint32 poly_msb = poly & (1 << 31);
+        poly <<= 1;
+        if (poly_msb) poly ^= iso_polynomial;
+    }
+
+    return hash ^ (initial_hash << 8);
+}
+
+// terse implementation of the POSIX CRC32 checksum algorithm
+// meant for the `cksum` utility, which can be used through
+// the GNU coreutils `cksum command`:
+// `echo -ne "string to hash" | cksum`
+// see: https://pubs.opengroup.org/onlinepubs/9799919799/utilities/cksum.html
+uint32
+crc32_posix(struct String str)
+{
+    uint32 hash = 0;
+    STRING_ITERATE(i, c, str)
+    {
+        hash = crc32_posix_iteration(hash, c);
+    }
+
+    uint32 length = string_length(str);
+    while (length) {
+        hash = ~crc32_posix_iteration(hash, length);
+        length >>= 8;
+    }
+
+    return hash;
+}