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

Ну, да. Если у нас множество четных и 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;
а уж детально вникать какой вариант из нескольких, наилучший, этот подвиг не для меня

 

rmn, algent, вернулся к этой задачке. В итоге сделал вот такое решение: https://github.com/HoShiMin/Ranger

 

• Если надо - помнится тестировал, но вторично вникать не буду.
• Код (ASM):

  1.  TetrTest:
  2.                        RdTSC        ; > eDx:eAx
  3.                     Mov  testTime0,eAx  ; сохранение TSC
  4.                     Mov  testTime0+4,eDx  ;
  5.         ClD
  6.         xOr  eAx,eAx
  7.         Mov  eDi,of_[BS]
  8.         Mov  eCx,10000h / 8 / 4
  9.    rep  StosD ; [ds:eDi]
  10.  
  11.       Mov  Cnt,0FFFFFFFFh  ; 0.071.017.920 uS  E8400   ;
  12.    _CklTest:               ; =.../2FF37A00h            ;
  13.       MovZx  eCx,B_[Cnt+1]  ; .AdrStart                ;
  14.       Mov    [AdrStart],eCx                            ;
  15.       Mov    [AdrEnd],eCx                              ;
  16.       MovZx  eCx,B_[Cnt]    ; Size                     ;
  17.       Add    [AdrEnd],eCx   ; может быть 255+255 Max   ;
  18.       Mov    [iSize], eCx                              ;
  19.       Inc    eCx                                       ;
  20.       Mov    [iQnt], eCx                               ;
  21.                                                        ;
  22.       MovZx  eSi,B_[Cnt+2]  ; Value                    ;
  23.       MovZx  eDi,B_[Cnt+3]  ; Msk0x                    ;
  24.       Mov    [Msk0x],eDi                               ;
  25.       And    eSi,eDi                                   ;
  26.       xOr    eDi,255        ; Msk1x  13.03.23          ;
  27.       Mov    [Msk1x],eDi                               ;
  28.       Or     eDi,eSi                                   ;
  29.  
  30. ;   ;          0001000000000000                        ;
  31. ;   ; Mov  Cnt,1010000010011001y                       ;
  32. ;   ;              0000    1001                        ;
  33. ;   ;          1010    1001                            ;
  34. ;   ;          <St><Sz><Vl><Ms>                        ;
  35. ;   ;                      0110                        ;
  36. ;     Mov  Cnt,0FFFFh   ; SMV  память  MVS           ;
  37. ;  _CklTest:                                           ;
  38. ;     MovZx  eCx, B_[Cnt+1]  ; .AdrStart Size          ;
  39. ;     Mov    eAx, eCx                                  ;
  40. ;     And    eAx, 0Fh                                  ;
  41. ;     Mov    [iSize], eAx                              ;
  42. ;     SHR    eCx, 4                                    ;
  43. ;     Mov    [AdrStart], eCx                           ;
  44. ;     Add    eCx, eAx                                  ;
  45. ;     Mov    [AdrEnd], eCx  ; Это может быть 15+15 Мах ;
  46. ;     Inc    eAx                                       ;
  47. ;     Mov    [iQnt], eAx                               ;
  48. ;                                                      ;
  49. ;     MovZx  eSi,B_[Cnt]   ; Msk0x Value               ;
  50. ;     Mov    eDi,eSi                                   ;
  51. ;     SHR    eDi,4         ; Msk0x                     ;
  52. ;     Mov    [Msk0x],eDi                               ;
  53. ;     And    eSi,eDi       ; Val_Min                   ;
  54. ;     xOr    eDi,0Fh       ; Msk1x  13.03.23           ;
  55. ;     Mov    [Msk1x],eDi                               ;
  56. ;     Or     eDi,eSi       ; Val_Max                   ;
  57.  
  58. invokeXP _ForWASM,eSi,eDi,AdrStart,AdrEnd
  59.  
  60. ;       Mov [Found],0        ; oooo
  61. ;       JNC NotFound         ;
  62. ;       Mov [Found], 1       ; oooo
  63. ;       Mov eCx, [Cnt]       ;
  64. ;       BT_s D_[BS], eCx     ; бит карта 1=есть
  65. ;  NotFound:                 ;
  66.         MovZx  eCx, [qIter]       ;
  67.         Add    [qIterAll], eCx    ;
  68.     Mov [AdrExit],$               ; oooo
  69.     JL  DiagnoseExit              ; oooo
  70.         Cmp     Cl, [qIterMax]    ;
  71.        cMovL   eCx, D_[qIterMax]  ; oooo
  72.         Mov    [qIterMax], Cl     ;
  73.  
  74.         Dec  Cnt
  75.    ;    JNL  _CklTest   ;
  76.         JNZ  _CklTest  ;
  77.  
  78.   Call _TimeConsole
  79.  
  80.         Mov [AdrExit],$   ; oooo
  81.         Jmp DiagnoseExit  ; oooo
  82. ;
  83. ;
  84. ;
  85. _ForWASM  Proc  Val_Min:Dword,Val_Max:Dword,aStart:Dword,aEnd:Dword
  86.     Mov     [qIter], 0  ; oooo
  87.  
  88.     Mov     eSi, [Val_Min]  ; ??
  89.     Mov     eDi, [Val_Max]  ; ??
  90.  
  91.     Cmp     eSi, [aEnd]
  92.     JA     _3
  93.     Cmp     eSi, [aStart]
  94.     JAE    _2
  95.  
  96.     Cmp     eDi, [aStart]
  97.     JB     _3
  98.     Cmp     eDi, [aEnd]
  99.     JBE    _2
  100.  
  101. ;   Ret   ;  0.056.045.076 uS  E8400
  102.  
  103.  
  104.     Sub     [aEnd], eSi    ;;;;
  105.     Sub     eDi, eSi       ;;;
  106.     Sub     [aStart], eSi  ;;
  107.     xOr     eSi, eSi       ; упрощает (см. _6: /.../   JZ     _2), скорость?
  108.  
  109.     Mov     eDx, [Msk1x]
  110.  
  111.   ; Inc     [qIterAll]  ;  без  этого Inc после /????
  112.     Mov     eCx, [iQnt]
  113.     Cmp     eCx, 3   ; 3 =26E0/03E0  можно выбрать другое < qIter
  114.     JBE    _5
  115.  
  116.     BSR     eAx, eDx  ;  =3BF0/18F0 1.320 uS  без этого  всего =3980 1.326 uS
  117.     xOr     eBx,eBx
  118.     Inc     eAx       ;;
  119.     BT_s    eBx, eAx  ; старая .1... Msk1x * 2
  120.     Sub     eBx,eDx   ; Наибольший Void
  121.     Cmp     eBx, [iQnt]
  122.     JBE    _2         ; <= qnt
  123.  
  124.     Mov     [qIterMax+4],1  ; oooo
  125. ; Microsoft
  126. _1:
  127.     BSR     eCx, eDx
  128.   ; BSF     eCx, eDx  ; Так ошибки
  129.     JZ     _3         ; ../Test_Ou4.ttr
  130.     Inc     [qIter]     ; oooo
  131.     Mov     eBx, eSi
  132.     BT_c    eDx, eCx
  133.     BT_s    eBx, eCx
  134. ;  BT_n    eBx, eCx
  135.     Cmp     [aStart], eBx
  136.    cMovA    eSi, eBx
  137.     SetA     Ch           ; 0 1 0
  138.     Cmp     [aEnd], eBx
  139.    cMovB    eDi, eBx      ; 1 0 0
  140.     SetAE    Cl           ; 0 1 1
  141.     LoopD  _1
  142. _2:        ; Found
  143.     StC
  144.     Ret
  145. _5:
  146.     Mov     eAx, [aStart]
  147. _6:      ; В общем случае iSize/2 не поможет
  148.     Mov     eBx, eAx
  149.     And     eBx, [Msk0x]
  150.     JZ     _2
  151.     Inc     eAx
  152.     LoopD  _6
  153. _3:        ; NotFound
  154.     ClC
  155.     Ret
  156. _ForWASM  EndP
  157. ; Microsoft
  158.