Quickest way to encode vector of floats into hex or base64binary

Question

Right now, I'm doing it like this:

//encoding
std::vector<float> data = ...
const unsigned char* bytes = reinterpret_cast<const unsigned char*>(&data[0]);
std::vector<unsigned char> byteVec(bytes, bytes + sizeof(float) * data.size());
std::string newData = base64_encode(&byteVec[0], byteVec.size());



//decoding
std::vector<unsigned char> decodedData = base64_decode(newData);
unsigned char* bytes = &(decodedData[0]);    // point to beginning of memory
float* floatArray = reinterpret_cast<float*>(bytes);
std::vector<float> floatVec(floatArray, floatArray + decodedData.size() / sizeof(float));

The encoding takes 0.04 seconds, and the decoding takes 0.08 seconds. This is WAY too long. Is there a faster method?

I'm using a base64 library I found online, but if there is a faster method by using hex instead, I am definitely open to that!

The functions I use are the ones found in this answer.

EDIT: I also couldn't find a way to convert to/from hex for this vector, so any solutions for that would be very appreciated.

EDIT: All the time is in the encode/decode functions. None of it is the conversion of vectors/arrays or bytes/floats.

`std::vector data = base64_encode(&byteVec[0], byteVec.size());` seems wrong... Are you sure this is really what you are doing? — Holt, Aug 04 '17 at 13:45
Are you aware that base64 and hexadecimal output of bytes are different encodings? (though both are "lossless" and thus reversible.) — Scheff's Cat, Aug 04 '17 at 13:46
Why not simply `base64_encode((BYTE const*)data.data(), sizeof(float) * data.size());`? This would avoid unwanted copies... — Holt, Aug 04 '17 at 13:48
@Holt yes, and this encoding/decoding works. Why does it seem wrong? — anc, Aug 04 '17 at 14:00
@Holt oh wow, the base64_encode part was right, I edited the storing part. Sorry, updated! Also, thanks for your suggestion! It ended up not making a difference, unfortunately? — anc, Aug 04 '17 at 14:03
@anc, how much data are you working with? What kind of hardware are you working on? Where is the time actually spent? Allocating memory? Copying? Conversion? Validation? I suggest that if you are serious about improving performance here, write a small complete program that deals with data similar to your actual workload and start profiling-modifying- profiling again until you reach an acceptable performance. — yzt, Aug 04 '17 at 14:50
Questions like this is unlikely to have an answer unless you have a [mcve]. We can speculate all we want but we won't be able to say anything concrete. — Passer By, Aug 04 '17 at 17:46
@PasserBy I honestly thought what I provided was one. What are things I should add? — anc, Aug 04 '17 at 17:53
@anc I can't take the code you provided and see the results you claim. That is incomplete and not verifiable. — Passer By, Aug 04 '17 at 18:15
you can search for any open source library base64 on gihthub. https://github.com/search?l=C%2B%2B&o=desc&q=base64&s=stars&type=Repositories&utf8=%E2%9C%93 — Sahib Yar, Aug 07 '17 at 14:41
For encoding you might check this for fast conversion of 4 bytes to 8 digits at a time: https://stackoverflow.com/questions/45598583/efficient-conversion-of-a-binary-number-to-hexadecimal-string/45601966#45601966 — Mark Ransom, Aug 11 '17 at 20:18

geza · Accepted Answer · 2017-08-11T15:01:54.597

Here's code converting from/to hex.

On my machine, encoding is 12x faster, decoding is 3.3x faster than the routines you linked.

If you're willing to release the requirements a little bit, decode can be made 30% faster, if the format is not hex, but characters [a-p].

There is no error checking in the decode routine. It can be done at the cost of speed.

Note: do you compile with optimization enabled? I ask this because I can only reproduce your timing numbers with disabled optimizations. With optimization enabled, encode is slower than decode. With optimization disabled, encode is 2x faster then decode (like your results).

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

void hexEncode(void *output, const void *input, size_t size) {
    static const char table[256][2] = {
        {'0','0'},{'0','1'},{'0','2'},{'0','3'},{'0','4'},{'0','5'},{'0','6'},{'0','7'},{'0','8'},{'0','9'},{'0','a'},{'0','b'},{'0','c'},{'0','d'},{'0','e'},{'0','f'},
        {'1','0'},{'1','1'},{'1','2'},{'1','3'},{'1','4'},{'1','5'},{'1','6'},{'1','7'},{'1','8'},{'1','9'},{'1','a'},{'1','b'},{'1','c'},{'1','d'},{'1','e'},{'1','f'},
        {'2','0'},{'2','1'},{'2','2'},{'2','3'},{'2','4'},{'2','5'},{'2','6'},{'2','7'},{'2','8'},{'2','9'},{'2','a'},{'2','b'},{'2','c'},{'2','d'},{'2','e'},{'2','f'},
        {'3','0'},{'3','1'},{'3','2'},{'3','3'},{'3','4'},{'3','5'},{'3','6'},{'3','7'},{'3','8'},{'3','9'},{'3','a'},{'3','b'},{'3','c'},{'3','d'},{'3','e'},{'3','f'},
        {'4','0'},{'4','1'},{'4','2'},{'4','3'},{'4','4'},{'4','5'},{'4','6'},{'4','7'},{'4','8'},{'4','9'},{'4','a'},{'4','b'},{'4','c'},{'4','d'},{'4','e'},{'4','f'},
        {'5','0'},{'5','1'},{'5','2'},{'5','3'},{'5','4'},{'5','5'},{'5','6'},{'5','7'},{'5','8'},{'5','9'},{'5','a'},{'5','b'},{'5','c'},{'5','d'},{'5','e'},{'5','f'},
        {'6','0'},{'6','1'},{'6','2'},{'6','3'},{'6','4'},{'6','5'},{'6','6'},{'6','7'},{'6','8'},{'6','9'},{'6','a'},{'6','b'},{'6','c'},{'6','d'},{'6','e'},{'6','f'},
        {'7','0'},{'7','1'},{'7','2'},{'7','3'},{'7','4'},{'7','5'},{'7','6'},{'7','7'},{'7','8'},{'7','9'},{'7','a'},{'7','b'},{'7','c'},{'7','d'},{'7','e'},{'7','f'},
        {'8','0'},{'8','1'},{'8','2'},{'8','3'},{'8','4'},{'8','5'},{'8','6'},{'8','7'},{'8','8'},{'8','9'},{'8','a'},{'8','b'},{'8','c'},{'8','d'},{'8','e'},{'8','f'},
        {'9','0'},{'9','1'},{'9','2'},{'9','3'},{'9','4'},{'9','5'},{'9','6'},{'9','7'},{'9','8'},{'9','9'},{'9','a'},{'9','b'},{'9','c'},{'9','d'},{'9','e'},{'9','f'},
        {'a','0'},{'a','1'},{'a','2'},{'a','3'},{'a','4'},{'a','5'},{'a','6'},{'a','7'},{'a','8'},{'a','9'},{'a','a'},{'a','b'},{'a','c'},{'a','d'},{'a','e'},{'a','f'},
        {'b','0'},{'b','1'},{'b','2'},{'b','3'},{'b','4'},{'b','5'},{'b','6'},{'b','7'},{'b','8'},{'b','9'},{'b','a'},{'b','b'},{'b','c'},{'b','d'},{'b','e'},{'b','f'},
        {'c','0'},{'c','1'},{'c','2'},{'c','3'},{'c','4'},{'c','5'},{'c','6'},{'c','7'},{'c','8'},{'c','9'},{'c','a'},{'c','b'},{'c','c'},{'c','d'},{'c','e'},{'c','f'},
        {'d','0'},{'d','1'},{'d','2'},{'d','3'},{'d','4'},{'d','5'},{'d','6'},{'d','7'},{'d','8'},{'d','9'},{'d','a'},{'d','b'},{'d','c'},{'d','d'},{'d','e'},{'d','f'},
        {'e','0'},{'e','1'},{'e','2'},{'e','3'},{'e','4'},{'e','5'},{'e','6'},{'e','7'},{'e','8'},{'e','9'},{'e','a'},{'e','b'},{'e','c'},{'e','d'},{'e','e'},{'e','f'},
        {'f','0'},{'f','1'},{'f','2'},{'f','3'},{'f','4'},{'f','5'},{'f','6'},{'f','7'},{'f','8'},{'f','9'},{'f','a'},{'f','b'},{'f','c'},{'f','d'},{'f','e'},{'f','f'}
    };

    const unsigned char *s = static_cast<const unsigned char *>(input);
    char *t = static_cast<char *>(output);
    const unsigned char *e;

    e = static_cast<const unsigned char *>(input) + (size&~3);
    while (s<e) {
        int v0 = s[0];
        int v1 = s[1];
        int v2 = s[2];
        int v3 = s[3];

        memcpy(t+0, table[v0], 2);
        memcpy(t+2, table[v1], 2);
        memcpy(t+4, table[v2], 2);
        memcpy(t+6, table[v3], 2);
        s += 4;
        t += 8;
    }

    e = static_cast<const unsigned char *>(input) + size;
    while (s<e) {
        memcpy(t, table[*s], 2);
        s++;
        t += 2;
    }
}

void hexDecode(void *output, const void *input, size_t size) {
    static const signed char table[128] = {
        -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
        -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
        -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
         0, 1, 2, 3, 4, 5, 6, 7, 8, 9,-1,-1,-1,-1,-1,-1,
        -1,10,11,12,13,14,15,-1,-1,-1,-1,-1,-1,-1,-1,-1,
        -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
        -1,10,11,12,13,14,15,-1,-1,-1,-1,-1,-1,-1,-1,-1,
        -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
    };
    const unsigned char *s = static_cast<const unsigned char *>(input);
    char *t = static_cast<char *>(output);
    const unsigned char *e;

    e = static_cast<const unsigned char *>(input) + (size&~3);
    while (s<e) {
        int v0 = table[s[0]];
        int v1 = table[s[1]];
        int v2 = table[s[2]];
        int v3 = table[s[3]];

        t[0] = v0<<4|v1;
        t[1] = v2<<4|v3;

        s += 4;
        t += 2;
    }

    e = static_cast<const unsigned char *>(input) + size;
    while (s<e) {
        int v0 = table[s[0]];
        int v1 = table[s[1]];

        *t = v0<<4|v1;

        s += 2;
        t++;
    }
}

std::string hexEncodeToString(const void *input, size_t size) {
    std::string s;
    s.resize(size*2);
    // Note: const_cast'ing this maybe not standard conformant here
    hexEncode(const_cast<char *>(s.data()), input, size);
    return s;
}

std::vector<unsigned char> hexDecodeToVector(const std::string &input) {
    std::vector<unsigned char> s;
    s.resize(input.length()>>1);
    hexDecode(s.data(), input.data(), input.length());
    return s;
}


int main() {
    float in[2] = { 3.14f, 2.718f };

    std::vector<unsigned char> r = hexDecodeToVector(hexEncodeToString(in, sizeof(in)));
    const float *f = reinterpret_cast<float*>(r.data());

    for (size_t i=0; i<2; i++) {
        printf("%f\n", f[i]);
    }
}

Here's an [a-p] version:

void apEncode(void *output, const void *input, size_t size) {
    static const char table[256][2] = {
        {'a','a'},{'a','b'},{'a','c'},{'a','d'},{'a','e'},{'a','f'},{'a','g'},{'a','h'},{'a','i'},{'a','j'},{'a','k'},{'a','l'},{'a','m'},{'a','n'},{'a','o'},{'a','p'},
        {'b','a'},{'b','b'},{'b','c'},{'b','d'},{'b','e'},{'b','f'},{'b','g'},{'b','h'},{'b','i'},{'b','j'},{'b','k'},{'b','l'},{'b','m'},{'b','n'},{'b','o'},{'b','p'},
        {'c','a'},{'c','b'},{'c','c'},{'c','d'},{'c','e'},{'c','f'},{'c','g'},{'c','h'},{'c','i'},{'c','j'},{'c','k'},{'c','l'},{'c','m'},{'c','n'},{'c','o'},{'c','p'},
        {'d','a'},{'d','b'},{'d','c'},{'d','d'},{'d','e'},{'d','f'},{'d','g'},{'d','h'},{'d','i'},{'d','j'},{'d','k'},{'d','l'},{'d','m'},{'d','n'},{'d','o'},{'d','p'},
        {'e','a'},{'e','b'},{'e','c'},{'e','d'},{'e','e'},{'e','f'},{'e','g'},{'e','h'},{'e','i'},{'e','j'},{'e','k'},{'e','l'},{'e','m'},{'e','n'},{'e','o'},{'e','p'},
        {'f','a'},{'f','b'},{'f','c'},{'f','d'},{'f','e'},{'f','f'},{'f','g'},{'f','h'},{'f','i'},{'f','j'},{'f','k'},{'f','l'},{'f','m'},{'f','n'},{'f','o'},{'f','p'},
        {'g','a'},{'g','b'},{'g','c'},{'g','d'},{'g','e'},{'g','f'},{'g','g'},{'g','h'},{'g','i'},{'g','j'},{'g','k'},{'g','l'},{'g','m'},{'g','n'},{'g','o'},{'g','p'},
        {'h','a'},{'h','b'},{'h','c'},{'h','d'},{'h','e'},{'h','f'},{'h','g'},{'h','h'},{'h','i'},{'h','j'},{'h','k'},{'h','l'},{'h','m'},{'h','n'},{'h','o'},{'h','p'},
        {'i','a'},{'i','b'},{'i','c'},{'i','d'},{'i','e'},{'i','f'},{'i','g'},{'i','h'},{'i','i'},{'i','j'},{'i','k'},{'i','l'},{'i','m'},{'i','n'},{'i','o'},{'i','p'},
        {'j','a'},{'j','b'},{'j','c'},{'j','d'},{'j','e'},{'j','f'},{'j','g'},{'j','h'},{'j','i'},{'j','j'},{'j','k'},{'j','l'},{'j','m'},{'j','n'},{'j','o'},{'j','p'},
        {'k','a'},{'k','b'},{'k','c'},{'k','d'},{'k','e'},{'k','f'},{'k','g'},{'k','h'},{'k','i'},{'k','j'},{'k','k'},{'k','l'},{'k','m'},{'k','n'},{'k','o'},{'k','p'},
        {'l','a'},{'l','b'},{'l','c'},{'l','d'},{'l','e'},{'l','f'},{'l','g'},{'l','h'},{'l','i'},{'l','j'},{'l','k'},{'l','l'},{'l','m'},{'l','n'},{'l','o'},{'l','p'},
        {'m','a'},{'m','b'},{'m','c'},{'m','d'},{'m','e'},{'m','f'},{'m','g'},{'m','h'},{'m','i'},{'m','j'},{'m','k'},{'m','l'},{'m','m'},{'m','n'},{'m','o'},{'m','p'},
        {'n','a'},{'n','b'},{'n','c'},{'n','d'},{'n','e'},{'n','f'},{'n','g'},{'n','h'},{'n','i'},{'n','j'},{'n','k'},{'n','l'},{'n','m'},{'n','n'},{'n','o'},{'n','p'},
        {'o','a'},{'o','b'},{'o','c'},{'o','d'},{'o','e'},{'o','f'},{'o','g'},{'o','h'},{'o','i'},{'o','j'},{'o','k'},{'o','l'},{'o','m'},{'o','n'},{'o','o'},{'o','p'},
        {'p','a'},{'p','b'},{'p','c'},{'p','d'},{'p','e'},{'p','f'},{'p','g'},{'p','h'},{'p','i'},{'p','j'},{'p','k'},{'p','l'},{'p','m'},{'p','n'},{'p','o'},{'p','p'}
    };

    const unsigned char *s = static_cast<const unsigned char *>(input);
    char *t = static_cast<char *>(output);
    const unsigned char *e;

    e = static_cast<const unsigned char *>(input) + (size&~3);
    while (s<e) {
        int v0 = s[0];
        int v1 = s[1];
        int v2 = s[2];
        int v3 = s[3];

        memcpy(t+0, table[v0], 2);
        memcpy(t+2, table[v1], 2);
        memcpy(t+4, table[v2], 2);
        memcpy(t+6, table[v3], 2);
        s += 4;
        t += 8;
    }

    e = static_cast<const unsigned char *>(input) + size;
    while (s<e) {
        memcpy(t, table[*s], 2);
        s++;
        t += 2;
    }
}

void apDecode(void *output, const void *input, size_t size) {
    const unsigned char *s = static_cast<const unsigned char *>(input);
    char *t = static_cast<char *>(output);
    const unsigned char *e;

    e = static_cast<const unsigned char *>(input) + (size&~3);
    while (s<e) {
        int v0 = s[0]-'a';
        int v1 = s[1]-'a';
        int v2 = s[2]-'a';
        int v3 = s[3]-'a';

        t[0] = v0<<4|v1;
        t[1] = v2<<4|v3;

        s += 4;
        t += 2;
    }

    e = static_cast<const unsigned char *>(input) + size;
    while (s<e) {
        int v0 = s[0]-'a';
        int v1 = s[1]-'a';

        *t = v0<<4|v1;

        s += 2;
        t++;
    }
}

Thank you so much for this answer! I have this code to call the encode: `std::vector byteVec(bytes, bytes + sizeof(float) * data.size()); std::string str = ""; hexEncode(&str, &byteVec[0], byteVec.size());` — anc, Aug 11 '17 at 13:39
And yet I'm getting a segfault in the first while loop of encode, at the memcpy part. Do you know why this is? — anc, Aug 11 '17 at 13:39
You need to allocate space in the string beforehand, and use that space instead of `&str`. `str.resize(data.size()*2)`, and use `const_cast(str.data())` for the output parameter of hexEncode. I'm not sure, how standard conformant this is. Maybe you need to use a temporary vector instead, and use that for initializing the string — geza, Aug 11 '17 at 13:55
Could you possibly add an example to your answer? Although I'm no longer getting a segfault, what's returned from encode is an empty string. — anc, Aug 11 '17 at 14:04
@anc: I've added two helper functions, and a small example `main()` — geza, Aug 11 '17 at 14:14
Thank you so much, it worked!!! Out of curiosity, if the encoding was a-p instead of hex, would that make the converted string longer or shorter? — anc, Aug 11 '17 at 14:17
@anc: It would be the same size. Decode would be faster this way, because no table is needed. If you need a shorter encoding, then base64 is the way to go (I'm sure that you can find a more performant base64 encoder, than the version you linked). Or, there are even shorter encodings, like [base85](https://en.wikipedia.org/wiki/Ascii85) — geza, Aug 11 '17 at 14:45
Okay, awesome, thank you! If it's not too much work, would you mind posting the faster decoding? You can post it as a different answer if that's easier, but I already awarded the bounty on this one :) — anc, Aug 11 '17 at 14:50

Treebeard · Answer 2 · 2017-08-11T09:22:52.330

Try your benchmarks against this, it's tested code. I benchmarked the copy algorithm vs the move and copy comes back 25ms quicker on a 1 million element array. If this gives no improvement then you need to look into your encoder and decoder functions. If 0.04 seconds is too long it looks like your into the micro-optimisation realm. Maybe making an encoder which takes const iterators would yield positive results.

Post code and I'd be happy to edit this to answer better.

auto data = std::vector<float>( (1024 * 1024), 0.1f );

auto i_ptr = reinterpret_cast<std::uint8_t *>( data.data() );
auto i_len = data.size() * sizeof( float );
auto str = _base64_encode( i_ptr, i_len );


auto out = _base64_decode( str );

auto o_ptr = reinterpret_cast<float *>( out.data() );
auto o_len = out.size() / sizeof( float );

auto a_dest = std::vector<float>{};
std::copy( o_ptr, o_ptr + o_len, std::back_inserter( a_dest ) );

EDIT:

So I've been through the algorithm you linked and there is loads of scope for optimisation. For instance in the decode function, each iteration of the loop is doing 12 lookups in 4 if statements, only 1 of these ifs was not done in the previous iteration. Since the results of b4 feed into b3 then b4 can be effectively removed.

To be honest this is more of a Code Review question. And recommend reading is the Algoithms Lubrary and 'From mathematics to generic programming' by Alexander Stepanov.

Thank you for answering!! Are the underscores before the function names unintentional? — anc, Aug 09 '17 at 18:31
That's alright, was it any help? The underscore thing is just the way I write private functions, private variables have an underscore after them. — Treebeard, Aug 10 '17 at 15:16
what are you using to benchmark this? Have you tried [Google Benchmark](https://github.com/google/benchmark). Also what's the code for your encode and decode functions? — Treebeard, Aug 10 '17 at 17:36
I can't add that much code to the question, but it's exactly what is in the linked answer. — anc, Aug 10 '17 at 18:04

Quickest way to encode vector of floats into hex or base64binary

2 Answers2