countbits

count leading 0 bits in hex strings
git clone git://jb55.com/countbits
Log | Files | Refs

commit e9ddd02b83bcad88950ba6d25ae9e1dc10e9c90d
Author: William Casarin <jb55@jb55.com>
Date:   Fri,  6 May 2022 08:24:54 -0700

countbits

Signed-off-by: William Casarin <jb55@jb55.com>

Diffstat:
A.gitignore | 5+++++
AMakefile | 4++++
Ahex.h | 69+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Amain.c | 119+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Aproof.h | 26++++++++++++++++++++++++++
5 files changed, 223 insertions(+), 0 deletions(-)

diff --git a/.gitignore b/.gitignore @@ -0,0 +1,5 @@ +.build-result +.buildcmd +countbits +shell.nix +.envrc diff --git a/Makefile b/Makefile @@ -0,0 +1,4 @@ + + +countbits: main.c + $(CC) $< -o $@ diff --git a/hex.h b/hex.h @@ -0,0 +1,69 @@ + +static inline int char_to_hex(unsigned char *val, char c) +{ + if (c >= '0' && c <= '9') { + *val = c - '0'; + return 1; + } + if (c >= 'a' && c <= 'f') { + *val = c - 'a' + 10; + return 1; + } + if (c >= 'A' && c <= 'F') { + *val = c - 'A' + 10; + return 1; + } + return 0; +} + +static inline int hex_decode(const char *str, size_t slen, void *buf, size_t bufsize) +{ + unsigned char v1, v2; + unsigned char *p = buf; + + while (slen > 1) { + if (!char_to_hex(&v1, str[0]) || !char_to_hex(&v2, str[1])) + return 0; + if (!bufsize) + return 0; + *(p++) = (v1 << 4) | v2; + str += 2; + slen -= 2; + bufsize--; + } + return slen == 0 && bufsize == 0; +} + +static inline size_t hex_str_size(size_t bytes) +{ + return 2 * bytes + 1; +} + +static inline char hexchar(unsigned int val) +{ + if (val < 10) + return '0' + val; + if (val < 16) + return 'a' + val - 10; + abort(); +} + +static inline int hex_encode(const void *buf, size_t bufsize, char *dest, size_t destsize) +{ + size_t i; + + if (destsize < hex_str_size(bufsize)) { + fprintf(stderr, "hexencode: destsize(%zu) < hex_str_size(%zu)\n", destsize, hex_str_size(bufsize)); + return 0; + } + + for (i = 0; i < bufsize; i++) { + unsigned int c = ((const unsigned char *)buf)[i]; + *(dest++) = hexchar(c >> 4); + *(dest++) = hexchar(c & 0xF); + } + *dest = '\0'; + + return 1; +} + diff --git a/main.c b/main.c @@ -0,0 +1,119 @@ +#include <stdio.h> +#include <string.h> +#include <stdlib.h> + +static inline int char_to_hex(unsigned char *val, char c) +{ + if (c >= '0' && c <= '9') { + *val = c - '0'; + return 1; + } + if (c >= 'a' && c <= 'f') { + *val = c - 'a' + 10; + return 1; + } + if (c >= 'A' && c <= 'F') { + *val = c - 'A' + 10; + return 1; + } + return 0; +} + +static inline int hex_decode(const char *str, size_t slen, void *buf, size_t bufsize) +{ + unsigned char v1, v2; + unsigned char *p = buf; + + while (slen > 1) { + if (!char_to_hex(&v1, str[0]) || !char_to_hex(&v2, str[1])) + return 0; + if (!bufsize) + return 0; + *(p++) = (v1 << 4) | v2; + str += 2; + slen -= 2; + bufsize--; + } + return slen == 0 && bufsize == 0; +} + +static inline size_t hex_str_size(size_t bytes) +{ + return 2 * bytes + 1; +} + +static inline char hexchar(unsigned int val) +{ + if (val < 10) + return '0' + val; + if (val < 16) + return 'a' + val - 10; + abort(); +} + +static inline int hex_encode(const void *buf, size_t bufsize, char *dest, size_t destsize) +{ + size_t i; + + if (destsize < hex_str_size(bufsize)) { + fprintf(stderr, "hexencode: destsize(%zu) < hex_str_size(%zu)\n", destsize, hex_str_size(bufsize)); + return 0; + } + + for (i = 0; i < bufsize; i++) { + unsigned int c = ((const unsigned char *)buf)[i]; + *(dest++) = hexchar(c >> 4); + *(dest++) = hexchar(c & 0xF); + } + *dest = '\0'; + + return 1; +} + + +static inline int zero_bits(unsigned char b) +{ + int n = 0; + + if (b == 0) + return 8; + + while (b >>= 1) + n++; + + return 7-n; +} + +/* find the number of leading zero bits in a hash */ +static int count_leading_zero_bits(unsigned char *hash, int len) +{ + int bits, total, i; + + for (i = 0, total = 0; i < len; i++) { + bits = zero_bits(hash[i]); + total += bits; + if (bits != 8) + break; + } + return total; +} + +int main(int argc, const char *argv[]) +{ + unsigned char buf[4096]; + const char *hex; + int bits, len; + + if (argc < 1) + return 1; + + hex = argv[1]; + len = strlen(hex); + + if (!hex_decode(hex, len, buf, len/2)) + return 2; + + bits = count_leading_zero_bits(buf, len / 2); + printf("%d\n", bits); + return 0; +} diff --git a/proof.h b/proof.h @@ -0,0 +1,26 @@ +static inline int zero_bits(unsigned char b) +{ + int n = 0; + + if (b == 0) + return 8; + + while (b >>= 1) + n++; + + return 7-n; +} + +/* find the number of leading zero bits in a hash */ +static int count_leading_zero_bits(unsigned char *hash) +{ + int bits, total, i; + + for (i = 0, total = 0; i < 32; i++) { + bits = zero_bits(hash[i]); + total += bits; + if (bits != 8) + break; + } + return total; +}