Converting large bit strings to hexadecimal in C

user_16640162 0
Viewed 115

I need to convert large bit string like this :

unsigned char* key = "0111010111010101010101010100101011010";

to hexadecimal strings like this :

unsigned char* string = EBAAAA95A;

The problem is that my keys are usually longer than 50 or 60 bits, and when I try to convert them with strtoll(key, NULL, 2), the returned number is far bigger than what a long long int can even hold. Is there an efficiant way to convert this into hexadecimal directly ?

Thanks a lot for your help !

cryptography ansi hex binary c
3 Answers

I think you need to roll your own implementation. Here's one implementation taking inspiration from @mediocrevegetable

#include <stdlib.h>
#include <string.h>

static inline int bitstr_to_int(const char *str, int len)
{
        int h = 0;
        for (int i = 0; i < len; i++) {
                switch (str[i]) {
                        case '0': h *= 2; continue;
                        case '1': h *= 2; h++; continue;
                        default: return -1;
                }
        }
        return h;
}

char * bitstr_to_hexstr(const char *str, int len)
{
        static const char hex_digit[] = {
                '0', '1', '2', '3',
                '4', '5', '6', '7',
                '8', '9', 'A', 'B',
                'C', 'D', 'E', 'F'
        };

        int i = 0; //traces the input chars in bitstr
        int j = 0; //traces the output chars in hexstr
        int h = 0;
        int r = len % 4;
        int q = len / 4;

        char *hexstr = malloc(q + !!r + 1);
        if (hexstr == NULL) return NULL;

        if (r != 0) {
                h = bitstr_to_int(str, r);
                if (h == -1) goto err;
                hexstr[j++] = hex_digit[h];
        }

        for (i = r; i < len; i += 4) {
                h = bitstr_to_int(str+i, 4);
                if (h == -1) goto err;
                hexstr[j++] = hex_digit[h];
        }

        hexstr[j] = '\0';
        return hexstr;
err:
        free(hexstr);
        return NULL;
}

int main(void)
{
    const char *key = "0111010111010101010101010100101011010";

    char *res = bitstr_to_hexstr(key, strlen(key));
    printf("%s\n", res);
}
user_15235550

If you need to work with big numbers, a good library (perhaps the library of choice) is GMP. Here's a simple example demonstrating the conversion you asked about:

#include <stdio.h>
#include <gmp.h>

int main()
{
    char *instr = "0111010111010101010101010100101011010";
    char outstr[100];
    mpz_t x;
    mpz_init(x);
    mpz_set_str(x, instr, 2);                     /* convert from base 2 */
    printf("%s\n", mpz_get_str(outstr, 16, x));   /* convert to base 16 */
}
user_39238960

If the string is longer than 64 bits, you can convert one hex digit at a time, making sure only the first digit uses less than 4 bits.

Here is an implementation with test cases:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* convert len bits to a number */
static unsigned bin2hex_val(const char *str, size_t len) {
    unsigned v = 0;
    while (len --> 0) {
        v = v * 2 + (*str++ - '0');
    }
    return v;
}

char *bin2hex_str(const char *str) {
    static const char hex_digits[16] = "0123456789ABCDEF";
    size_t len = strspn(str, "01"); /* number of binary digits */
    size_t hexlen = (len + 3) / 4;     /* number of hex digits */
    char *p = malloc(hexlen + 1);   /* allocate the hex string */
    size_t i = 0;

    if (p) {
        /* special case the first hex digit if fewer than 4 bits */
        if (len % 4) {
            p[i++] = hex_digits[bin2hex_val(str, len % 4)];
            str += len % 4;
            len -= len % 4;
        }
        /* convert remaining groups of 4 bits as hex digits */
        while (len > 0) {
            p[i++] = hex_digits[bin2hex_val(str, 4)];
            str += 4;
            len -= 4;
        }
        p[i] = '\0';
    }
    return p;
}

void test(const char *str) {
    char *p = bin2hex_str(str);
    printf("%s -> %s\n", str, p);
    free(p);
}

int main() {
    test("");
    test("0");
    test("1");
    test("01");
    test("011");
    test("0111");
    test("01110");
    test("011101");
    test("0111010");
    test("01110101");
    test("01110101110101010101010101001010");
    test("0111010111010101010101010100101011010011101011101010101010101010");
    test("01110101110101010101010101001010110100111010111010101010101010100101011010");
    test("ABC");
    test("0.0");
    test("123");
    return 0;
}

Output:

 ->
0 -> 0
1 -> 1
01 -> 1
011 -> 3
0111 -> 7
01110 -> 0E
011101 -> 1D
0111010 -> 3A
01110101 -> 75
01110101110101010101010101001010 -> 75D5554A
0111010111010101010101010100101011010011101011101010101010101010 -> 75D5554AD3AEAAAA
01110101110101010101010101001010110100111010111010101010101010100101011010 -> 1D755552B4EBAAAA95A
ABC ->
0.0 -> 0
123 -> 1
user_45932670
Related