How do you spot or avoid committing off-by-one errors?

522 views Asked by At

When I write code, among the more common classes of bug I create is off-by-one errors (OBO). In "real" code I most often run into this issue while doing complicated pointer/iterator arithmetic in C or C++, but I've also at times had issues with it in job interview and homework (e.g. implementing mergesort) questions where I used other programming languages.

My typical debugging strategy consists of randomly swapping < and <=, ++var and var++ and appending + 1 or - 1 to variables until the code appears to work. I would be interested to know what better strategies or tools (e.g. static analysis, debugger/IDE features, etc.) exist to spot OBO.

I'm not particularly interested in pat answers like "avoid C-style loops," "avoid pointer arithmetic," "code in a functional style" or "use a different programming language." Yes, these things can mitigate the issue, but it's not always possible to do them and they don't eliminate the OBO danger entirely.

As an example, I believe the following code, a C (or it's also valid C++) implementation of strcpy(3), is free of OBO. But as you can see there are dozens of potential problem areas where OBO could crop up. Is there some way to easily confirm that it is in fact free of OBO?

#include <stdbool.h>
#include <stdint.h>
#include <string.h>

#if !defined(__GNUC__) && !defined(__attribute__)
#define __attribute__(X)
#endif

#ifdef __cplusplus
extern "C" {
#if defined(__GNUC__) || defined(_MSC_VER) || defined(__restrict)
#define restrict __restrict
#elif !defined(restrict)
#define restrict
#endif
#endif

static inline bool aligned8(const void *ptr) {return !((uintptr_t)ptr & 7);}
static inline bool aligned4(const void *ptr) {return !((uintptr_t)ptr & 3);}
static inline bool aligned2(const void *ptr) {return !((uintptr_t)ptr & 1);}

/* Positive return value is the greatest common alignment (≤8) of the pointers.
 * Negative return value is the byte offset that when added to both pointers
 * yields a pair of pointers with alignment ≥8.
 */
static inline int common_alignment(const void *p1, const void *p2) {
    if (aligned8(p1)) {
        if (aligned8(p2))
            return 8;
        else if (aligned4(p2))
            return 4;
        else if (aligned2(p2))
            return 2;
    } else if (aligned4(p1)) {
        if (aligned8(p2))
            return 4;
        else if (aligned4(p2))
            return -4;
        else if (aligned2(p2))
            return 2;
    } else if (aligned2(p1)) {
        if (aligned4(p2))
            return 2;
        else if (aligned2(p2))
            return -6;
    } else if (!aligned2(p2)) {
        return -7;
    }
    return 1;
}

/* strcpy implementation
 */
__attribute__((nonnull))
size_t string_copy(char *restrict dst, const char *restrict src) {
    size_t i = 0;
    int align = common_alignment(dst, src);

    if (align < 0) {
        for (; i < (size_t)-align; ++i)
            if (!(*dst++ = *src++))
                return i;
        align = 8;
    }

    const size_t mask = (size_t)align - 1;

#define ALIGNED_STRING_COPY_IMPL_(BITS) do {\
    uint##BITS##_t *restrict dst##BITS = (uint##BITS##_t*)dst;\
    while (*src++)\
        if (!(++i & mask))\
            *dst##BITS++ = *(const uint##BITS##_t *restrict)(src - align);\
    dst = (char*)dst##BITS;\
} while (0)

    if (align & 8) {
        ALIGNED_STRING_COPY_IMPL_(64);
    } else if (align & 4) {
        ALIGNED_STRING_COPY_IMPL_(32);
    } else if (align & 2) {
        ALIGNED_STRING_COPY_IMPL_(16);
    } else { // byte-aligned
        while ((*dst++ = *src++))
            ++i;
        return i;
    }

    const size_t offset = (i & mask) + 1;

    memcpy(dst, src - offset, offset);

    return i;
}

#ifdef __cplusplus
}
#endif
0

There are 0 answers