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

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

Метки:
  1. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.234
    Ну, да. Если у нас множество четных и begin == 0x1234567, size == 1, то сразу true... :)

    Множество не непрерывное, а разреженное, между элементами есть пропуски и весь диапазон begin..end может находиться между парой соседних элементов множества не пересекаясь с ними.
     
  2. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    5.699
    судя по логике, привязка идёт не к адресу, а к базе..
    MTRR.PhysBase = Addr - Offset = Addr & MTRR.PhysMask // маска просто тупо нулит офсет в верхней части регистра.
     
  3. algent

    algent Member

    Публикаций:
    0
    Регистрация:
    11 апр 2018
    Сообщения:
    81
    Задача, блин, хрен поймёшь чё надо :)
    Мой вариант:
    1. вычисляем (value & mask). Если (value & mask) > begin + size, то сразу возвращаем 0. Иначе,
    2. интервал чисел [begin, begin + size) заменяем на новый рабочий интервал чисел [begin - (value & mask), begin + size - (value & mask))
    3. Работаем с битами "?". Сначала отбрасываем каждый старший из них, который в одиночку, больше чем begin + size - (value & mask).
    4. Перебираем комбинации оставшихся бит "?", на попадание в интервал чисел [begin - (value & mask), begin + size - (value & mask))
    начинаем с сочетания всех единиц, типа 1__1___11__11, и далее уменьшаем:
    1__1___11__10
    1__1___11__01
    1__1___11__00
    1__1___10__11,
    после каждого шага, проверяем и продолжаем пока, комбинация_бит > begin - (value & mask).
    Ну, ессно, если случится что, комбинация_бит =< begin + size - (value & mask)), возвращаем 1.
    Пожалуй, уменьшать можно ускоренно.
    Сам тестировать не буду :)
     
  4. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.234
    algent,
    Так и сделано в примере выше (только без сдвига диапазона влево) :)
     
  5. R81...

    R81... Active Member

    Публикаций:
    0
    Регистрация:
    1 фев 2020
    Сообщения:
    117
    А не простой ли это перебор - логарифм-то где?
     
  6. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.234
    HoShiMin,
    Можно в начало проверок еще пару шагов с O(1) добавить:
    Код (C):
    1.  
    2. bool intersects (Range* range, type_t begin, type_t end)
    3. {
    4.     type_t minValue, maxValue;
    5.     /*
    6.         За O(1) проверяем варианты:
    7.               [begin  end]
    8.         [Set]
    9.  
    10.               [begin  end]
    11.                            [Set]
    12.  
    13.               [begin  end]
    14.               [    Set   ]
    15.  
    16.         За O(N) (N - количество нулевых бит в маске) проверяем только:
    17.               [begin  end]
    18.             [     Set      ]
    19.     */
    20.     if (range->mask == 0)
    21.         return true;
    22.    
    23.     if (range->mask == ~0)
    24.         return (range->value >= begin && range->value <= end);
    25.        
    26.     minValue = range->value;
    27.     maxValue = range>value | ~range->mask;
    28.    
    29.     if (maxValue < begin || minValue > end)
    30.         return false;
    31.    
    32.     if (begin <= minValue && end >= maxValue)
    33.         return true;
    34.    
    35.     /* дальше тело функции LongTest */
    36.     ...
    37. }
    38.  
     
  7. R81...

    R81... Active Member

    Публикаций:
    0
    Регистрация:
    1 фев 2020
    Сообщения:
    117
    Код (Text):
    1.  000000E9  EB 78                  Jmp    TetrTest
    2. 000000EB            _ForWASM  Proc  Val_Min:Dword,Val_Max:Dword,aStart:Dword,aEnd:Dword
    3. = eSi                ValxMin   Equ eSi
    4. = eDi                ValxMax   Equ eDi
    5.  
    6. 000000EB  55           *        push   ebp
    7. 000000EC  8B EC       *        mov    ebp, esp
    8. 000000EE  8B 75 08            Mov     ValxMin, [Val_Min]  ; ???
    9. 000000F1  8B 7D 0C            Mov     ValxMax, [Val_Max]  ; ???
    10.  
    11. 000000F4  3B 75 14            Cmp     ValxMin, [aEnd]
    12. 000000F7  77 4D            JA     _3
    13. 000000F9  3B 75 10            Cmp     ValxMin, [aStart]
    14. 000000FC  72 43            JB     _2
    15.  
    16. 000000FE  3B 7D 10            Cmp     ValxMax, [aStart]
    17. 00000101  72 43            JB     _3
    18. 00000103  3B 7D 14            Cmp     ValxMax, [aEnd]
    19. 00000106  77 39            JA     _2
    20.  
    21. = eDx                xMsk1    Equ eDx
    22. 00000108  8B D6            Mov     xMsk1, ValxMin  ;;
    23. 0000010A  33 D7            xOr     xMsk1, ValxMax  ;
    24.  
    25.                 ; (aStart And xMsk1) Or  Val_Min в нем (установим возможные 11 из aStart)
    26. 0000010C  8B CA            Mov     eCx, xMsk1    ; ;;;  0111 1111  0111 1111   0111 1110  0111 1110
    27. 0000010E  23 4D 10            And     eCx, [aStart] ; ;;   x011 1111s x010 0000s  x011 1110s x010 0001s
    28.                                           ;      0011 1111  0010 0000   0011 1110  0010 0000
    29. 00000111  0B F1            Or      ValxMin, eCx  ; ;    x000 0000^ x000 0000^  x000 000x^ x000 0000^
    30.                                           ;      x011 1111  x010 0000   x011 111x  x010 000x
    31.                 ; (aEnd   Or NxMsk1) And Val_Max в нем (установим возможные 00 из aEnd)
    32. 00000113  8B CA            Mov     eCx, xMsk1    ; ;;;  0111 1111  0111 1111   0111 1110  0111 1110
    33. 00000115  F7 D1            Not     eCx ;xMsk0    ;      1000 0000  1000 0000   1000 0001  1000 0001
    34. 00000117  0B 4D 14            Or      eCx, [aEnd]   ; ;;   x011 1111e x010 0000e  x011 111xe x010 000xe
    35.                                           ;      1011 1111  1010 0000   1011 1111  1010 0001
    36. 0000011A  23 F9            And     ValxMax, eCx  ; ;    x111 1111v x111 1111v  x111 111xv x111 111xv
    37.                                           ;      x011 1111  x010 0000   x011 111x  x010 000x
    38.                 ; Одинаковые биты в ValxMin и ValxMax не надо обрабатывать - как 00 в xMsk1!
    39. 0000011C  8B D6            Mov     xMsk1, ValxMin  ;;
    40. 0000011E  33 D7            xOr     xMsk1, ValxMax  ;
    41.                 ; Microsoft
    42. 00000120             _1:
    43. 00000120  0F BD CA            BSR     eCx, xMsk1
    44. 00000123  74 26            JZ     _4
    45. 00000125  8B DE            Mov     eBx, ValxMin
    46. 00000127  0F B3 CA            BT_c    xMsk1, eCx
    47. 0000012A  0F AB CB            BT_s    eBx, eCx
    48. 0000012D  39 5D 10            Cmp     [aStart], eBx
    49. 00000130  0F 47 F3           cMovA    ValxMin, eBx              ; ..1000  ..0000
    50. 00000133  0F 97 C5            SetA     Ch           ; 0 1 0
    51. 00000136  39 5D 14            Cmp     [aEnd], eBx
    52. 00000139  0F 42 FB           cMovB    ValxMax, eBx  ; 1 0 0     ; ..1111  ..1000
    53. 0000013C  0F 93 C1            SetAE    Cl           ; 0 1 1
    54. 0000013F  E2 DF            LoopD  _1
    55. 00000141             _2:        ; Found
    56. 00000141  F9                StC
    57.                     Ret
    58. 00000142  C9           *        leave
    59. 00000143  C2 0010       *        ret    00010h
    60. 00000146             _3:        ; NotFound
    61. 00000146  F8                ClC
    62.                     Ret
    63. 00000147  C9           *        leave
    64. 00000148  C2 0010       *        ret    00010h
    65. 0000014B             _4:        ;  Тестовая проверка
    66. 0000014B  3B F7            Cmp     ValxMin, ValxMax
    67. 0000014D  0F 87 00000095        JA      Err
    68. 00000153  3B 75 10            Cmp     ValxMin, [aStart]
    69. 00000156  0F 93 C5            SetAE    Ch             ; 0 1 0 1
    70. 00000159  3B 7D 14            Cmp     ValxMax, [aEnd] ;
    71. 0000015C  0F 96 C1            SetBE    Cl             ; 1 0 0 1
    72. 0000015F  E3 E5            JeCxZ  _3
    73. 00000161  EB DE            Jmp    _2
    74. 00000163            _ForWASM  EndP
    75.                 ;
    76. 00000163             TetrTest:
    77. 00000163  0F 31                               RdTSC        ; > eDx:eAx
    78. 00000165  A3 00004090 R                        Mov  testTime0,eAx  ; сохранение TSC
    79. 0000016A  89 15 00004094 R                        Mov  testTime0+4,eDx  ;
    80. 00000170  FC                    ClD
    81. 00000171  33 C0                xOr  eAx,eAx
    82. 00000173  BF 00000030 R            Mov  eDi,of_[BS]
    83. 00000178  B9 00000800                Mov  eCx,10000h / 8 / 4
    84. 0000017D  F3/ AB           rep  StosD ; [ds:eDi]
    85.  
    86. 0000017F  B8 0000FFFF              Mov  eAx,0FFFFh                                  ;
    87. 00000184               _CklTest:                                           ;
    88. 00000184  0F B6 CC              MovZx  eCx,Ah  ; .AdrStart Size                  ;
    89. 00000187  89 0D 0000403C R          Mov    [AdrEnd],eCx                              ;
    90. 0000018D  83 25 0000403C R          And    [AdrEnd],0Fh ; Size                       ;
    91.        0F
    92. 00000194  C1 E9 04              SHR    eCx,4                                     ;
    93. 00000197  89 0D 00004038 R          Mov    [AdrStart],eCx                            ;
    94. 0000019D  01 0D 0000403C R          Add    [AdrEnd],eCx ; Это может быть 15+15 Мах   ;
    95.                                                                        ;
    96. 000001A3  0F B6 F0              MovZx  eSi,Al  ; .xMsk0 Value                    ;
    97. 000001A6  8B FE              Mov    eDi,eSi                                   ;
    98. 000001A8  83 E6 0F              And    eSi,0Fh ; Value                           ;
    99. 000001AB  C1 EF 04              SHR    eDi,4   ; xMsk0                           ;
    100. 000001AE  23 F7              And    eSi,eDi                                   ;
    101. 000001B0  F7 D7              Not    eDi     ; xMsk1                           ;
    102. 000001B2  0B FE              Or     eDi,eSi                                   ;
    103.  
    104.                 ;     Mov  eAx,0FFFFFFFFh                              ;
    105.                 ;  _CklTest:                                           ;
    106.                 ;     MovZx  eCx,Ah  ; .AdrStart Size                  ;
    107.                 ;     Mov    [AdrStart],eCx                            ;
    108.                 ;     Mov    [AdrEnd],eCx                              ;
    109.                 ;     MovZx  eCx,Al  ; Size                            ;
    110.                 ;     Add    [AdrEnd],eCx                              ;
    111.                 ;                                                      ;
    112.                 ;     ROR    eAx,16                                    ;
    113.                 ;     MovZx  eSi,Al  ; Value                           ;
    114.                 ;     MovZx  eDi,Ah  ; xMsk0                           ;
    115.                 ;     And    eSi,eDi                                   ;
    116.                 ;     Not    eDi     ; xMsk1                           ;
    117.                 ;     Or     eDi,eSi                                   ;
    118.                 ;     ROL    eAx,16                                    ;
    119.  
    120.                  invokeXP _ForWASM ,eSi,eDi,AdrStart,AdrEnd
    121. 000001B4  FC             1                ClD
    122.                  1  
    123. 000001B5  FF 35 0000403C R *        push   AdrEnd
    124. 000001BB  FF 35 00004038 R *        push   AdrStart
    125. 000001C1  57           *        push   edi
    126. 000001C2  56           *        push   esi
    127. 000001C3  E8 FFFFFF23       *        call   _ForWASM
    128.                  1     invoke   _ForWASM,eSi,eDi,AdrStart,AdrEnd
    129. 000001C8  73 07                JNC NotFound
    130. 000001CA  0F AB 05                BT_s D_[BS],eAx  ; бит карта 1=есть
    131.        00000030 R
    132. 000001D1             NotFound:
    133. 000001D1  48                    Dec  eAx
    134.                      ;  JNL  _CklTest
    135. 000001D2  75 B0                JNZ  _CklTest
    136.  
    --- Сообщение объединено, 11 мар 2023 ---
    ; Как отлаживаться-тo. И ускоритель этот у меня не убыстряет.
     
    Последнее редактирование: 11 мар 2023
  8. algent

    algent Member

    Публикаций:
    0
    Регистрация:
    11 апр 2018
    Сообщения:
    81
    А я смотрю у HoShiMin`а чё то не запускается, не отлаживается и решил, что тема ещё актуальна.

    Я или пропустил, или поленился в самом начале поставить:
    if (size >= mask)
    return true;
    а уж детально вникать какой вариант из нескольких, наилучший, этот подвиг не для меня :)