Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have some code for checking a binary header to see if a binary file is meant to be read by a certain program, and I could use some extra eyes to review it.

Assume the following typedefs:

namespace Types
{
    using Byte = std::uint8_t;      // From <cstdint>
    using UInt32 = std::uint32_t;
    using String = std::string;     // From <string>
}

// This is a vector of bytes loaded from a binary file.
using ByteBuffer = std::vector<Types::Byte>;    // From <vector>

Also assume the following constants:

namespace Constants
{
    const Types::String     G_BINARY_HEADER_STRING  = "A2FORMAT";
    const Types::Byte       G_BINARY_MAJOR_VERSION  = 0x00;
    const Types::Byte       G_BINARY_MINOR_VERSION  = 0x01;
    const Types::UInt32     G_BINARY_HEADER_SIZE    = 14;
}

Here is the binary-header-validating code:

bool isBufferValid (ByteBuffer &a_buffer)
{
    // Get the size of the buffer. Make a cursor here, too.
    Types::UInt32 l_size = a_buffer.size();
    Types::UInt32 l_cursor = 0;

    // Check to see if the size exceeds 14 bytes.
    if (l_size <= Constants::G_BINARY_HEADER_SIZE)
        return false;

    // Bytes #1 to #8 are the characters in the binary header string.
    for (l_cursor = 0; l_cursor < Constants::G_BINARY_HEADER_STRING.size(); ++l_cursor)
    {
        if (a_buffer.at(l_cursor) != Constants::G_BINARY_HEADER_STRING.at(l_cursor))
        {
            return false;
        }
    }

    // Byte #9 indicates the engine's major version.
    //
    // If the byte found doesn't match the current major version, then it is invalid.
    if (a_buffer.at(8) != Constants::G_BINARY_MAJOR_VERSION)
        return false;

    // Byte #10 indicates the engine's minor version.
    //
    // If this byte given is greater than the current minor version, then it is invalid.
    if (a_buffer.at(9) > Constants::G_BINARY_MINOR_VERSION)
        return false;

    // Bytes #11 through #14 make up a 32-bit unsigned integer that indicates how many
    // bytes of data reside after the binary header.
    //
    // These bytes are arranged in Little Endian Notation.
    Types::UInt32 l_sizeOfData = 0;
    for (Types::UInt32 i = 0, j = 10; j < 14; i++, j++)
        l_sizeOfData |= a_buffer.at(j) << (i * 8);

    // If the amount of bytes in the buffer, after the header, do not match the number found
    // in the integer above, then the buffer is invalid.
    if (l_size - Constants::G_BINARY_HEADER_SIZE != l_sizeOfData)
        return false;

    // Remove the header from the buffer, because it has been confirmed valid, and is
    // therefore ready to use.
    a_buffer.erase(a_buffer.begin(), a_buffer.begin() + Constants::G_BINARY_HEADER_SIZE);

    return true;
}

Is there anything I can do to make this code more efficient? Are there also any steps I can take to make this validation more effective?

share|improve this question
1  
Please don't change the code in the question as that might invalidate answers. I've rolled back the changes, and ask of you to read what you may and may not do when receiving answers – holroy Feb 28 at 18:17
    
Minor quibble: endianness isn't a notation per se. – Lightness Races in Orbit Feb 28 at 23:21
up vote 5 down vote accepted

Is there anything I can do to make this code more efficient?

The first step is to ditch the vector, and specifically the .erase call at the end.

Calling erase on the head of a vector means performing a copy of the full buffer; it can, at best, be optimized to a memmov, but because of the header size (14 bytes) it cannot be vectorized, this really adds insult to injury.

In general, for parsing, I recommend using a slice: a lightweight container containing just the length of the content and a pointer to this content... owned by another container (maybe vector, maybe unique_ptr<[]>, ... ). Using a slice also allows abstracting the underlying storage, and that's sweet!

So, let's redefine ByteBuffer to:

template <typename T>
class Buffer {
public:
    ///
private:
    size_t size;
    T* data;
};

using ByteBuffer = Buffer<Byte const>;

Also, for style points, let's avoid modifying the arguments of the validation function. Since now ByteBuffer does not allocate, it comes at no extra cost:

boost::optional<ByteBuffer> check_and_strip_header(ByteBuffer const& input) {
}

Note: ideally, a variant ByteBuffer or Error would be the most expressive return, in a pinch boost::optional<ByteBuffer> just mimicks your current interface, and if not including boost matters, just returning an empty ByteBuffer on failure should work just fine... also then you lose the distinction between empty and failure.

Note: the type-freak in me would like to point out that using a different type for a raw buffer and the validated buffer would not be amiss either; a simple wrapper MyFileType containing a ByteBuffer for a result would help here. It would ensure that business logic supposed to be executed on a validated file cannot accidentally take a raw one instead.

Are there also any steps I can take to make this validation more effective?

You are using a lot of manual loops, which may cost performance (unless the compiler recognizes it) and certainly hinders readability but more importantly there is a lot of repetition in the prefix checking, and since you are about to parse files this repetition will probably continue further.

So let us start with a few helper methods on ByteBuffer:

//  Checks whether input starts with prefix.
bool starts_with(ByteBuffer const& input, ByteBuffer const& prefix) {
    if (buffer.size() < prefix.size()) { return false; }

    return memcmp(input.data(), prefix.data(), prefix.size()) == 0;
}

//  Split the buffer into at the specified position.
//  If the position is out of range, returns (input, empty).
std::pair<ByteBuffer, ByteBuffer> split_at(ByteBuffer const& input, size_t const pos) {
    if (pos > input.size()) { return std::make_pair(input, ByteBuffer()); }

    return std::make_pair(
        ByteBuffer(input.data(), pos),
        ByteBuffer(input.data() + pos, input.size() - pos)
    );
}

//  On success, returns the remaining bytes
//  On failure (if prefix isn't a prefix), returns none
boost::optional<ByteBuffer> strip_prefix(ByteBuffer const& input,
                                         ByteBuffer const& prefix)
{
    if (not starts_with(input, prefix)) { return boost::none; }

    return split_at(input, prefix.size()).second;
}

//  On success, returns (remaining bytes, number read).
//  On failure (buffer too short), returns (none, 0).
std::pair<boost::optional<ByteBuffer>, Types::UInt32> read_u32_le(ByteBuffer const& input) {
    if (input.size() < 4) { return std::make_pair(boost::none, 0); }

    auto const splitted = split_at(input, 4);

    //  Note: on a LE architecture, this should be optimized
    //        to a simple memcpy by the compiler (or better).
    Types::UInt32 const number =
        splitted.first[0] << (0 * 8) |
        splitted.first[1] << (1 * 8) |
        splitted.first[2] << (2 * 8) |
        splitted.first[3] << (3 * 8);

    return std::make_pair(splitted.second, number);
}

Now that we have the helper methods, we will also alter the set of constants: checking a single constant is faster than checking individual ones, and having a pre-calculated "total" length is risky in the face of change. So here we go:

namespace Constants {
    Byte const G_BINARY_HEADER_STORAGE[] = "A2FORMAT\x00\x01";

    ByteBuffer const G_BINARY_HEADER{G_BINARY_HEADER_STORAGE, sizeof(G_BINARY_HEADER_STORAGE)-1};
}

And now, let's go!

boost::optional<ByteBuffer> check_and_strip_header(ByteBuffer const& input) {
{
    //  Check the header string and version fields at once
    boost::optional<ByteBuffer> buffer = strip_prefix(input, G_BINARY_HEADER);

    if (not buffer) { return boost::none; }

    //  Check the size of the data
    Types::UInt32 l_sizeOfData = 0;
    std::tie(buffer, l_sizeOfData) = read_u32_le(*buffer);

    if (not buffer) { return boost::none; }

    if (buffer->size() != l_sizeOfData) { return boost::none; }

    //  Success!
    return buffer;
}

We are relying on the compiler to inline the necessary bits. This means that the definition of the helper methods should be inline in the ByteBuffer header file, to avoid the overhead of function calls.

share|improve this answer
    
"a lot of manual loops" there are two – Lightness Races in Orbit Feb 28 at 23:23
    
Why do you rename the function to check_and_strip_header when it no longer strips? – Lightness Races in Orbit Feb 28 at 23:23
    
ByteBuffer const G_BINARY_HEADER = ByteBuffer(G_BINARY_HEADER_STORAGE, sizeof(G_BINARY_HEADER_STORAGE)); Why copy-initialisation? Just ByteBuffer const G_BINARY_HEADER{G_BINARY_HEADER_STORAGE, sizeof(G_BINARY_HEADER_STORAGE)}; is clearer and more direct. It also does not require the type to be copy-constructible. – Lightness Races in Orbit Feb 28 at 23:26
    
read_u32_le contains a syntax error in one of the comments (and this is indicated by the syntax highlighter) – Lightness Races in Orbit Feb 28 at 23:27
    
check_and_strip_header is now quite hard to follow. At least add some more comments but I found the OP's original code to be much easier to read. – Lightness Races in Orbit Feb 28 at 23:27

The most unforgivable fault with this function is that calling isValidBuffer() also erases the buffer! That completely violates the Principle of Least Surprise. If anything, the parameter should be const.

share|improve this answer
1  
It doesn't erase the whole buffer, though. It only erases the first 14 bytes of the buffer, which is the binary header that has, by that point, been confirmed to be a valid buffer by the program. Regardless, I will make that a const parameter and outsource that task from the function. – Dennis Feb 28 at 17:58
12  
It's still unforgivable. If a method is named isSomething(), my expectation is that it returns true or false with no side-effects. – 200_success Feb 28 at 18:00
1  
I wouldn't erase it at all. Its size is negligible but you're requiring a move of every single byte of your payload. Just start examining your data from where the header left off. – Lightness Races in Orbit Feb 28 at 23:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.