c++ - 使用 16 位计数器检测多个窗口/轨道是否与单个窗口重叠

Question

我得到多个轨道（称为窗口），具有开始和结束时间戳以及具有相同的窗口。我需要检查是否有任何轨道时间戳与此窗口时间戳匹配。所有时间戳都是 16 位格式。这些时间戳是从同一个单调时钟生成的。

进程_1：

track_start -> get_data(clock_monotonic) & 0xFFFF

track_end -> get_data(clock_monotonic) & 0xFFFF

进程_2：

window_start -> get_data(clock_monotonic) & 0xFFFF

window_end -> get_data(clock_monotonic) & 0xFFFF

进程_3：

检测轨道是否与窗口匹配？

问题是 16 位翻转。下面是我的算法来解决这个问题：

1. 获取 64 位的当前时间戳，称为“当前”

2. 轨道和窗口的所有时间戳都转换为 ('current'&0xFFFFFFFFFFFF0000) | 时间戳，即较低的 16 位 LSB 被时间戳取代。

3. 如果开始 > 结束（翻转问题），我们只使用开始时间戳并添加差异。所以新的结束时间戳 = end + (0xFFFF - start) + end + 1。查看代码中的 remap 函数。

4. 这是有效的，因为 Process_3 将获得最大延迟为 1 分钟的轨道和窗口时间戳。

    #include <chrono>
    #include <cstdint>
    #include <iostream>
    #include <thread>
    #include <stdlib.h>     /* srand, rand */
    #include <vector>
    #include <time.h>       /* time */
    #include <unistd.h>
    #include <assert.h>
   
    using namespace std;
   
    auto getTimeStampCount() {
        struct timespec ts;
        clock_gettime( CLOCK_MONOTONIC, &ts );
        return (uint64_t)ts.tv_sec * 1000000000U + (uint64_t)ts.tv_nsec;
    }
   
    /* returns tuples in this format <16bit start, 16bit end, real 64bit start, real 64bit end> */
    auto generateTimeStamp() {
        auto ms = getTimeStampCount();
        int x = ms & 0xFFFF;
        //generate a random number between 1 and 65535
        int randomNumber = rand() % 65535 + 1;
        int y = (x + randomNumber) & 0xFFFF;/
        return make_tuple(x, y, ms, ms + randomNumber);
    }
   
    bool isOverlapping(tuple<int64_t, int64_t> a, tuple<int64_t, int64_t> b) {
        return get<0>(a) <= get<1>(b) && get<0>(b) <= get<1>(a);
    }
   
    //for printing tuples
    template<std::size_t> struct int_{};
   
    template <class Tuple, size_t Pos>
    std::ostream& print_tuple(std::ostream& out, const Tuple& t, int_<Pos> ) {
        out << std::get< std::tuple_size<Tuple>::value-Pos >(t) << ',';
        return print_tuple(out, t, int_<Pos-1>());
    }
   
    template <class Tuple>
    std::ostream& print_tuple(std::ostream& out, const Tuple& t, int_<1> ) {
        return out << std::get<std::tuple_size<Tuple>::value-1>(t);
    }
   
    template <class... Args>
    ostream& operator<<(ostream& out, const std::tuple<Args...>& t) {
        out << '(';
        print_tuple(out, t, int_<sizeof...(Args)>());
        return out << ')';
    }
   
    auto remap(int64_t currentTime, tuple<int64_t, int64_t, int64_t, int64_t> t) {
        int64_t mask = 0xFFFFFFFFFFFF0000; //to remove 16 lsb bits
        int64_t x = (currentTime & mask) | get<0>(t);
        int64_t y = (currentTime & mask) | get<1>(t);
        /* 
             *  Normal case: where x is less than y
             *                     ____x____________y______ 
             *                     <--------0xffff-------->
             *
             *  abnormal case: where x is greater than y
             *                     ____y____________x______ 
             *                     <--------0xffff-------->
         *  In the abnormal case just subtract 0xffff - x) + y + 1 to get the duration by which y increased
            */
        if(x > y) {
            int64_t increase = (0xFFFF - x) + y + 1;
            return make_tuple(x, y + increase);
        }
        return make_tuple(x, y);
    }
   
    int main ()
    {
        srand (time(NULL));
   
        //generate the timestamp for SSL
        vector<tuple<int64_t, int64_t, int64_t, int64_t> > tracks;
        for (int i = 0; i < rand()%5; i++) {
            tracks.push_back(generateTimeStamp());
        }
        for (int i = 0; i < tracks.size(); i++)
            cout << hex << "generated tracks " << tracks[i] << endl;
   
        //generate the timestamp for window
        auto window = generateTimeStamp();
        cout << hex << "generated window " << window << endl;
   
        auto currentTimeStamp = getTimeStampCount();
        cout << hex << "current timestamp " << currentTimeStamp << endl;
        //make sure currentTimeStamp is greater than current window timestamps and the difference between them is not more than 16 bits(approximately 1 minute)
        for (int i = 0; i < tracks.size(); i++) {
            if(currentTimeStamp <= get<3>(tracks[i]) || (get<2>(tracks[i]) - currentTimeStamp) >= 0xFFFF) {
                cout << "error " << "currentTimeStamp " << currentTimeStamp << "track " << tracks[i] << endl;
                exit(0);
            }
            if(currentTimeStamp <= get<3>(window) || (get<2>(window) - currentTimeStamp) >= 0xFFFF) {
                cout << "error " << "currentTimeStamp " << currentTimeStamp << "window " << window << endl;
                exit(0);
            }
        }
   
        //remapped tracks timestamps 
        std::vector<std::tuple<int64_t, int64_t>> remappedTracks;
        for (int i = 0; i < tracks.size(); i++) {
            remappedTracks.push_back(remap(currentTimeStamp, tracks[i]));
        }
   
        //remapped window timestamps 
        auto remappedWindow = remap(currentTimeStamp, window);
        cout << "remapped window " << hex << remappedWindow << endl;
   
        //check if window timestamps overlap with tracks timestamps
        for (int i = 0; i < tracks.size(); i++) {
            auto realTrackTimeStamps = make_tuple(get<2>(tracks[i]), get<3>(tracks[i]));
            auto realWindowTimeStamps = make_tuple(get<2>(window), get<3>(window));
            bool shouldBe = isOverlapping(realTrackTimeStamps, realWindowTimeStamps);
            bool got = isOverlapping(remappedTracks[i], remappedWindow);
            if (shouldBe != got) {
                cout << "generated track " << tracks[i] << endl;
                cout << "generated window " << window << endl;
                cout << "ramapped track " << remappedTracks[i] << endl;
                cout << "ramapped window " << remappedWindow << endl;
            }
            assert(shouldBe == got);
        }
    }
   

代码：https ://ideone.com/cpUrHL给出一些想法。这是模拟代码以提供视角。

有什么让它变得更好的想法或你能想到的任何错误吗？

注意：无法修改 Process_1 和 2 以传递附加信息，此时也无法更改 api。

标签： c++algorithmdatetimebit-manipulation64-bit