Быстрая проверка на пересечение диапазонов

Тема в разделе "WASM.A&O", создана пользователем HoShiMin, 5 мар 2023.

Метки:
  1. R81...

    R81... Active Member

    Публикаций:
    0
    Регистрация:
    1 фев 2020
    Сообщения:
    141
    Далее называемое ТС диапазоном, я назову множеством - {}.
    Меня данное определение ТС запутывает (корректность?).

    Без гарантий:
    Лучше логарифма..., единиц..., только в обратную сторону.

    Установим в элементе {e} биты, допускающие изменения,
    соотв. битам begin.
    Это будет к begin ближайший (<) или ближайший (>),
    но не факт, что ближайший вообще.

    ЕСЛИ {e} >= begin ТО
    ЕСЛИ {e} <= (begin + size) ТО пересечение найдено: выход. кЕСЛИ
    ИНАЧЕ найдем ближайший (>): {e} = {e} '+' {1}
    '+' естественно ТОЛЬКО по битам допускающим изменения.
    ЕСЛИ {e} <= (begin + size) ТО пересечение найдено: выход. кЕСЛИ
    кЕСЛИ
    пересечение не найдено: выход.

    P.S. Я в си и вообще в скриптах "не копенгаген", а на Asm
    и сами можете проверить - ваша же задача.
    --- Сообщение объединено, 9 мар 2023 ---
    Ошибся - нашел контрпримеры - не получаются ближайшие так просто.
     
    Последнее редактирование: 9 мар 2023
  2. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    а что мешает изменить принцип маски и тем самым получить более простое да быстрое решение? тормознутая маска - это ж совсем дно :)
     
  3. R81...

    R81... Active Member

    Публикаций:
    0
    Регистрация:
    1 фев 2020
    Сообщения:
    141
    Может быть искать ближайший итерационно: делением пополам оставшегося подмножества {}, но там опять же логарифм(((.
     
  4. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.328
    UbIvItS,
    Ну, давай, обгони мой пример по скорости. А то я вообще не понимаю, что такое "тормознутая маска" и как изменить ее принцип :)

    Можно псевдокодом и для 4-битных чисел, чтобы многабуков не читать.
    Вот множество (value 1100, mask 1100):
    1100
    1101
    1110
    1111
    Проверяемый диапазон: begin 0001, end 0100.

    Как тут будет выглядеть "быстрая" маска?
     
  5. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    rmn, ну - во1ых отказываемся от value и у нас что за задача? выяснить есть ли пересечения. задаём маски и определяем расстояние..
    M1 = [m1] [m2] [m3] [m4] // mask 1
    M2 = [m21] [m22] [m23] [m24] // mask 2
    max_domain = new dom(4) // dom is 4-bit number
    min_domain = new dom(4)
    sub = new dom(4)
    D = [d1] [d2] [d3] [d4]
    tst = [t1] [t2] [t3] [t4]
    =======
    rst1 = M1 ^ tst
    rst2 = M2 ^ tst
    max_domain(i) = max(rst1, rst2, i) | i=1..4
    min_domain(i) = min(rst1, rst2, i) | i=1..4
    sub(i) = max_domain(i) - min_domain(i) | i=1..4
    [sub(i) > get_domain(D, i)] then NoIntersect() | i=1..4
    otherwise GotIntersect();
    >>>>>>>>>>>>
    для начала как-то так :)
     
  6. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.328
    UbIvItS,
    а теперь конкретные нули и единички проставь вместо переменных для множества выше, чтобы видно было, что оно работает :)
     
  7. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    неа, пущай другие ставят, кому оное требуется :)
     
  8. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.328
    А, ну тогда понятно :)
     
  9. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    а что тебе собсно не по нраву? обычный скучно-линейный алго. иль ошибку узрел? :)
     
  10. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.328
    Пока я не узрел, что он вообще способен решить поставленную задачу. Больше смахивает на какую-то псевдонаучную х.ету :)
     
  11. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    Тебе что именно непонятно? :)
     
  12. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.328
    Непонятно, чему должны быть равны M1 ,M2, min_domain, max_domain, D, tst, sub, чтобы определить принадлежность элементов множества
    1100
    1101
    1110
    1111
    диапазону 0001..0100.

    И, что самое главное: как M1, M2, min_domain, max_domain, D, tst и sub должны быть получены из пары 1100 & 1100.

    Вот такая малость, остальное, вроде, понятно :)
     
  13. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    rmn, схема ТС приводит к проблемам, поэтому я и предложил другую схему. подходит ли ему эта другая схема - Вопрос. и, конечно, входные данные несовместимые.
    M1 и М2 - ручной ввод, задаёт маски фильтрации.
    D - ручной ввод, задаёт расстояние между векторами.
    tst - ручной ввод, алго проверяет наличие этого вектора в двух множествах. вектор tst принадлежит двум множествам, если расстояние между векторами rst1 & rst2 < D.
    вот отображение tst для каждого множества.
     
  14. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.328
    UbIvItS,
    А, ну то есть, твой мотор решает какую-то твою, не имеющую никакого отношения к ТС задачу. Ясно, понятно :)
     
  15. HoShiMin

    HoShiMin Well-Known Member

    Публикаций:
    5
    Регистрация:
    17 дек 2016
    Сообщения:
    1.422
    Адрес:
    Россия, Нижний Новгород
    rmn, проверил со всеми правками (RangeBits, поменял местами min/max, добавил проверку на mask == 0) - и не работает :\
    Проверь на входных данных:
    Код (C):
    1.  
    2. 0000_0000 begin
    3. 0000_0001 end
    4.  
    5. 0000_0001 value
    6. 0000_0001 mask
    7. ============
    8. ????_???1 range
    9.  
    Должно вернуть true, твой вариант возвращает false.
     
  16. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.328
    Эх... придется все-таки компилить... :)
    --- Сообщение объединено, 10 мар 2023 ---
    HoShiMin,
    В функции MaybeIntersects должно быть && (range->value <= end)
    --- Сообщение объединено, 10 мар 2023 ---
    Так же, раз нам экстремальные значения множества известны, можно немного ускориться, написав в Intersects:
    Код (C):
    1.  
    2.     ...
    3.     result = Range_ComparePoint (range->value /* minPoint */, begin, end);
    4.  
    5.     if (result < 0)
    6.         return false;
    7.  
    8.     if (result == 0)
    9.         return true;
    10.  
    11.     result = Range_ComparePoint (range->value | ~range->mask /* maxPoint */, begin, end);
    12.     ...
    13.  
     
  17. algent

    algent Member

    Публикаций:
    0
    Регистрация:
    11 апр 2018
    Сообщения:
    101
    Че там проверять, конкретно в этом случае, если size >= 1, то сразу true.
    Если size = 0, то инвертировать (begin^value) & 1
    А если например, младший еденичный бит маски(И бит value в нём =1) весит больше чем, begin+size, то сразу 0
    ну и т.д.
     
  18. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    HoShiMin, так ты конкретизируй, где именно тебе весь этот маскарад нужен.
     
  19. HoShiMin

    HoShiMin Well-Known Member

    Публикаций:
    5
    Регистрация:
    17 дек 2016
    Сообщения:
    1.422
    Адрес:
    Россия, Нижний Новгород
    В x86 у нас есть набор MTRR-регистров, определяющих, какой тип кэширования будет иметь память:
    upload_2023-3-10_9-41-54.png

    Если выполняется условие (Addr & MTRR.PhysMask) == (MTRR.PhysBase & MTRR.PhysMask), значит к адресу применяется тип MTRR.Type.

    Мне надо составить таблички трансляций в EPT, а для этого необходимо каждой страничке прописать её тип.
    Сейчас это выглядит так:
    upload_2023-3-10_9-45-3.png

    Мы бежим по каждой страничке и получаем для неё тип на 49й и 60й строчках, проверяя каждую страничку той функцией для каждого MTRR, а затем "смешиваем" совпавшие типы.

    upload_2023-3-10_9-53-26.png

    Хочется немного оптимизировать: посчитать один раз тип, например для одного PDPTE или сразу для одного PDE, а для этого и необходимо искать такие пересечения, как в первом посте.
     
  20. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.074
    HoShiMin, и какие паттерны маски наиболее вероятны в твоём случае?