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

Ну, да. Если у нас множество четных и begin == 0x1234567, size == 1, то сразу true...

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

 

судя по логике, привязка идёт не к адресу, а к базе..
MTRR.PhysBase = Addr - Offset = Addr & MTRR.PhysMask // маска просто тупо нулит офсет в верхней части регистра.

 

Задача, блин, хрен поймёшь чё надо
Мой вариант:
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.
Пожалуй, уменьшать можно ускоренно.
Сам тестировать не буду

 

algent,
Так и сделано в примере выше (только без сдвига диапазона влево)

 

А не простой ли это перебор - логарифм-то где?

 

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.  

 

Код (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. И ускоритель этот у меня не убыстряет.

 

А я смотрю у HoShiMin`а чё то не запускается, не отлаживается и решил, что тема ещё актуальна.

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