Seth (zezu) wrote in dailysrc,
Seth
zezu
dailysrc

overlap with one output and two input ranges

This code determines whether one output buffer overlaps safely with two input buffers. One likely use would be the implementation of a variable length xor routine.

bcopy processes backwards from the end when write-ahead overlap would occur. the only addition here is checking to see if processing backwards for one range leads to write-ahead in the other input range. In that fatal case, you'd probably have to move one of the input ranges into a shunt.

Licensed under the GPL, per its source libozia.

At 115 lines this is a little long, but a lot of it is testing/reporting overhead. Tested on FreeBSD & MacOSX.


#include <iostream>
using namespace std;

const char *overlap_types[3] = { "moot", "reversable", "fatal" };
enum
{
        moot_overlap,
        reversable_overlap,
        fatal_overlap
};

template<typename T>
void trace_vector(T *p, char name, size_t n, size_t pad)
{
        size_t i;
        for (i = pad; i; i--)
                cout << ' ';
        for (i = n; i; i--)
                cout << name;
        cout << endl;
}

#define VET(d, l, r, n, exp) vet(d, l, r, n, exp, __FILE__, __LINE__)
template<typename T>
void vet(T *d, T *l, T *r, size_t n, int exp, const char *file, int line)
{
        int act;
        T *least;

        act = detect_overlap(d, l, r, n);
        if (act == exp)
                return;
        cout << file << ":" << line << " expected " << overlap_types[exp]
             << " overlap, got " << overlap_types[act]
             << endl;

        least = min(d, min(l, r));
        trace_vector(d, 'd', n, d - least);
        trace_vector(l, 'l', n, l - least);
        trace_vector(r, 'r', n, r - least);

        cout << endl;
}

template<typename T>
bool write_ahead_increment(const T *write, const T *read, size_t n)
{
        return (write > read && write < read + n);
}

template<typename T>
bool write_ahead_decrement(const T *write, const T *read, size_t n)
{
        write += n - 1;
        read += n - 1;
        return (write < read && write > read - n);
}

template<typename T>
int detect_overlap(const T *dst, const T *lhs, const T *rhs, size_t n)
{
        int ret;

        if (n == 0 || !(dst && (lhs || rhs)))
                return moot_overlap;

        ret = moot_overlap;

        if (write_ahead_increment(dst, lhs, n))
        {
                if (write_ahead_decrement(dst, rhs, n))
                        ret = fatal_overlap;
                else
                        ret = reversable_overlap;
        } 
        else if (write_ahead_increment(dst, rhs, n))
        {
                if (write_ahead_decrement(dst, lhs, n))
                        ret = fatal_overlap;
                else
                        ret = reversable_overlap;
        }
        
        return ret;
}


int main(int argc, char** argv)
{
        char *zero, *one, *two, *four, *five;

        one = zero + 1, two = one + 1, four = two + 2, five = four + 1;

        // write-behind of first range, second range beyond write range.
        VET(zero, one, five, 4, moot_overlap);

        // write-behind since reading comes first
        VET(one, one, five, 4, moot_overlap);

        // write-ahead in first range. second range beyond write range.
        VET(one, zero, five, 4, reversable_overlap);

        // write-ahead in first range, write-behind of second range.
        // processing in reverse causes write-ahead in second range.
        VET(one, zero, two, 4, fatal_overlap);
        
        // write-behind of first range, write-ahead in second range.
        // processing in reverse causes write-ahead in first range.
        VET(four, five, two, 4, fatal_overlap);

        cout << "done." << endl;
        exit(0);
}

Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments